1
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

I assume you want to only calculate shortest paths, starting from $s$, to vertices in its 3-hop neighborhood, i.e. vertices which are reachable from the start vertex $s$ with a path length $\leq 3$.

Use a limited breadth-first search and save the frontier vertices in a queue which is sorted according to its edge-weights. By doing that you have a priority queue and can update vertices like in the regular Dijkstra's algorithm. Note that you need to keep track of the current depth of the breadth-first search.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.