Finding the shortest path in a graph with teleports

user_16957088 0
Viewed 208

I have this graph problem I'm not sure how to approach.

I have an undirected graph with N vertices numbered 1-N. Every vertex numbered i has an arbitrary "rank" that can be anywhere from 1-i. Multiple vertices can have the same rank.

When traversing the graph, any vertex with rank r can instantly teleport/traverse to another vertex with the same rank r. This means unconnected components are still "connected" if at least one vertex from component A has the same rank as a vertex from component B.

How do I calculate the minimum amount of vertices needed to traverse from vertex A to vertex B?

My very naive solution is to add every edge that connects every equal-ranked vertex together to the graph, then applying a standard path-finding algorithm. This has a ridiculously long time complexity but I can't figure out a more efficient way to solve this.

Any help please?

graph optimization algorithm
1 Answers

adding all edges between same rank nodes is too slow as you have noticed - in worst case as close to all nodes are same rank it goes to O(n^2)

A way to solve this is to introduce new nodes for each rank and connect all nodes of same rank to one of new nodes (i.e. for nodes with rank 1 connect to node n+1 and so on).

Then you can consider new nodes to be of weight 0 when traversing to them - that way you can simply do 0-1 BFS with a dequeue (adding 0 weight nodes to front and other ones to the end once encountered) - this is linear so its solve-able in O(n)

user_40591450
Related