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

, , No Comments
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

Answered By : prabushitha

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) 
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60432

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback