Single-Source Shortest Path algorithm using Greedy technique

 Algorithm ShortestPaths(v,cost,dist,n)

{

for i :=1to n do

{

S[i]:=false; dist[i]:=cost[v,i];

}

S[v]:=true; dist[v] :=0.0;

{

Choose u from among those vertices not in S such that dist[u]is minimum; S[u]:=true;// Put u in S.

for (each w adjacent to u with S[w]= false)do

{

if

{

dist[w] >dist[u]+cost[u, w])) then dist[w] :=dist[u]+cost[u, w];

}

}

}

}

Source Code:

def dj(graph,src):

dist=[99 for i in range(len(graph))] visited=[False for i in range(len(graph))] for i in range(len(graph)):

if(graph[src][i]<=dist[i]): dist[i]=graph[src][i]

dist[src]=0 visited[src]=True count=0

 

while(count<len(graph)): min=99

for i in range(len(graph)): if(visited[i]==False and min>dist[i]):

min=dist[i] v=i

visited[v]=True count=count+1

for i in range(len(graph)): if(dist[i]>dist[v]+graph[v][i]):

dist[i]=dist[v]+graph[v][i]

 

for i in range(len(dist)):

print("The distance from ",src," to ",i," is ",dist[i])

 

graph=[

[0,10,99,3,99],

[99,0,2,1,99],

[99,99,0,99,71],

[99,4,8,0,2],

[99,99,9,99,0]]

dj(graph,0)