Single source shortest path | Dijkstra’s Algorithms

Single source shortest path problem ( Dijkstra’s Algorithms )

Shortest path problem is nothing but it is a problem of finding a path between two vertices or two nodes in a graph so that the sum of the weights of its constituent edges in graph is minimized.

  1. This problem is to determine shortest paths from a given source vertex v to all remaining destination vertices
  2. This problem can be solved by using Greedy method
  3. Edsger Dijkstra finds the shortest path between two given nodes and developed a solution called Dijkstra’s Algorithms For a given source node in the graph, the algorithm searches for the shortest path between this node and all others. This algorithm also be used to find shortest paths from a single node to a single destination node by stopping the algorithm once when the shortest path to the destination node has found
  4. Shortest paths are built one by one as a multi-stage solution
  5. Let S = set of vertices (including v0 ) to which the shortest paths have already been generated dist(w) = length of shortest path starting from v0, going through only those vertices that are in S, and ending at w
  6. If the next shortest path is to vertex u, then the path begins at v0, ends at u, and goes through only those vertices that are in S.
  7. The destination of the next path generated must be that of vertex u which has the minimum distance, dist(u), among all vertices not in S.
  8. Having selected a vertex u as in observation 2 and generated the shortest v0 to u path, vertex u becomes a member of S.
  9. An algorithm for Single source shortest path problem Using Dijkstra’s Algorithms  is given below:
    Algorithm ShortestPaths( v, cost, dist, n)
    {
    for ( i:= 1 to n ) do
    { // Initialize S.
    S[i] := false;
    dist[i] := cost[v,i];
    }
    S[v] := true;
    dist[v] := 0.0;
    for ( num := 2 to n ) do
    {
    // Determine n-1 paths from v.
    choose u from among those vertices not in S such that dist[u] is minimum;
    S[u] := true;
    for ( w :=1 to n ) do
    { //Update distances.
    if (( S[w]=false) and (dist[w] > dist[u] + cost[u,w])) then 
    dist[w] := dist[u] + cost[u,w];
    }
    }
    }
  10. Time complexity of Dijkstra’s algorithm is O(n2)


Example:

single source shortest path

Its cost adjacency matrix and shortest path values table are given below. In the cost adjacency matrix, all entries not shown are +.

single source shortest path

 

Topic : Single source shortest path | Dijkstra’s Algorithms

This Post Has One Comment

  1. wasihun

    nice site

Leave a Reply