Shortest Path Algorithm - Part 2

 Dijkstra’s Algorithm

•Given a graph and a source vertex in the graph, find the shortest paths from source to all vertices in the given graph.

•Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph.

•It is based on a greedy technique.

•Dijkstra's algorithm is applicable for:

»Both directed and undirected graphs

»All edges must have nonnegative weights

»Graph must be connected

Pseudocode

1.INITIALIZE-SINGLE-SOURCE(V, s)

2. S ←  Æ

3.Q ← V[G]

4. while Q ¹ Æ

5.      do u ← EXTRACT-MIN(Q)

6.           S ← S È {u}

7.           for each vertex v Î Adj[u]

8.                 do RELAX(u, v, w)

9.                 Update Q (DECREASE_KEY)

Dijkstra’s Algorithm Example

 

Time Complexity

• Running time: O(V2)

                   Application

         •It is used in finding the Shortest Path.

•It is used in geographical Maps.

•To find locations of Map which refers to vertices of graph.

•Distance between the location refers to edges.

•It is used in IP routing to find Open shortest Path First.

•It is used in the telephone network.