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.