# 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.