CODEWITHSUNDEEP
algorithmgraphfixed
sel
sel

Reputation: 493

Find shortest path of fixed hops between two node in a graph

if G = {V,E} is an undirected, connected, unweighted graph, and v is source vertex and u is destination vertex, I need to find shortest path between them. The problem is, I'm only allowed to move at fixed hops of size k. For example, if k = 3, reachable vertices from some vertex v are all the vertices that there exists a path of length 3 between them that doesn't traverse on the same edge twice. Each hop from v to u mustn't step on the same edge twice. However, a sequence of hops can move on the same edge several times. So far I've tried several approaches without any success, but I have a feeling that there's dynamic programming involved. Any ideas?

Upvotes: 1

Views: 545

Answers (1)

John Coleman
John Coleman

Reputation: 51998

One solution would be to create the graph G' = {V,E'} with the same vertex set as G but with the edge set consisting of the set of hops in the original graph, then using Dykstra's algorithm on G'.

Upvotes: 1

Related Questions