Dijkstra's algorithm, Data Structure & Algorithms

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.

 Ans:

The Dijkstra's algorithm: This is a problem which is concerned with finding the least cost path from an originating node in a weighted graph to a destination node in that particular graph.

The Dijkstra's algorithm is stated below:

Let G=(V,E) be the simple graph. Let a and z be any two vertices on the graph. Let L(x ) denotes the label of the vertex x which represent the length of shortest path from the vertex a to the vertex x and wij which denotes the weight of the edge eij=

1.  Let P=φ where  P is the set of those vertices which

Are having permanent labels and T={all vertices in graph}

 

Set L(a)=0,

L(x)=∞ for all x≠a

 

2.

Select the

label. This

vertex v in T which has

label is called permanent

the smallest

label of v.

Also set P=P {v} and T=T-{v}

If v=z then L(z) is the length of the shortest path from the vertex a to z and stop.

3.  If  v is  not equal to z    then   revise      the   labels    of vertices of T that is the vertices which do not consist of permanent labels.

The new label of vertex x in T can be given by

L(x)=min(old L(x), L(v)+w(v, x))

Here w(v, x) is the weight of the edge joining the vertex v and x. If there exists no direct edge joining v and x then take w(v, x)= ∞

4.  Repeat steps 2 and 3 until get the permanent z label.

Posted Date: 7/10/2012 6:38:52 AM | Location : United States







Related Discussions:- Dijkstra's algorithm, Assignment Help, Ask Question on Dijkstra's algorithm, Get Answer, Expert's Help, Dijkstra's algorithm Discussions

Write discussion on Dijkstra's algorithm
Your posts are moderated
Related Questions
3. A function to convert a complex number in algebraic form to a complex number in phasor form

whate is meant by the term heuristic

Ask question 1. Indicate whether each of the following properties is true for every Huffman code. a. The codewords of the two least frequent symbols have the same length. b. The

Z-Buffer Algorithm Also known as the Depth-Buffer algorithm, this image-space method simply selects for  display the polygon or portion of a polygon that is nearest to the view

Define Big Omega notation Big Omega notation (?) : The lower bound for the function 'f' is given by the big omega notation (?). Considering 'g' to be a function from the non-n

Spanning Trees: A spanning tree of a graph, G, refer to a set of |V|-1 edges which connect all vertices of the graph. There are different representations of a graph. They are f

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

The number of interchanges needed to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is 5