.
Single Source Shortest Path problem (SSSP) algorithm:
- Input: a weighted connected graph G =( V, E ), along with a node s designated as a source node. The weights tend to be symbolized through the 2D array (matrix) W[ 1:n,1:n ],
- where W[ i,j ] may be the weight associated with edge ( i,j ). If ( i,j ) isn't an edge, W[ i,j ] = infinity
- Note: W[ i.i ] = 0 for all i.
- Problem: Find the distance between s as well as each and every node in the graph.
- The greedy method here will need the particular explanations regarding several notion before it could be formulated.
- Let Y be a set, initially containg the single source node s.
- Definition: A path from s to a node x outside Y is called special when every intemediary node around the path belongs to Y.
- Let DIST[ 1:n ] be a real array in which DIST[ i ] = the length with the shortest special path from s to i
- Greedy selection policy: choose from all the nodes still outside Y the node of minimum DIST value, and also add it to Y.
- The claim, which will proved later, will be that all node in Y has is DIST value equal to the distance from it to s.
.