World's most popular travel blog for travel bloggers.

# [Solved]: modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

, ,
Problem Detail:

i want to modify Dijkstra algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

I tried it with BFS(breadth first search). Initially calculates the number of edges away from source to each vertex v. Then run Dijkstra's algorithm with a constraint like relaxation u if and only if edges size from the source to u is no longer than three. Is it correct or Are there another method to find it.(using Dijkstra algorithm)

###### Asked By : dulaj sanjaya

What if we add a simple if condition to check the parents since the number of parents to check is less (i.e. 3)?

In the dijkstra's algorithm,

``  Dijkstra(G,W,s)        Initialize_Single_Source(G,s)        S= {}        Q = V[G]        while Q != {} do           u = extract_min(Q)           S = S U {u}           for each vertex v element of Adj[u] do                 if(parent[u]==NIL || parent[u]==s || parent[parent[u]]==s)                      relax(u,v,w) ``