Question

10. You are given a directed graph G(V, E) where every vertex vi E V is associated with a weight wi> 0. The length of a path is the sum of weights of all vertices along this path. Given s,t e V, suggest an O((n+ m) log n) time algorithm for finding the shortest path m s toO As usual, n = IVI and m = IEI.

Answer 1

Algorithm goes like the below:

function Shortest_Path(list vertices, list edges, vertex src)
::dist[],pred[]

# 1): initialize graph
for each vertex v in vertices:
#In the Starting , all vertices have a weight of infinity
dist[v] := inf   
pred[v] := null   

#Except for the src, where the Weight is zero
dist[src] := 0   

# 2): relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if dist[u] + w < dist[v]:
dist[v] := dist[u] + w
pred[v] := u

# 3): check for negative-weight cycles
for each edge (u, v) with weight w in edges:
if dist[u] + w < dist[v]:
error "negative weight cycle found"
return dist[], pred[]