Minimum path in an undirected graph with locked and unlocked edges

2
votes

Given an undirected graph with positive weights, there are 2 kinds of edges: locked edges and unlocked edges. Determination if a given edge is either locked or unlocked edge takes O(1).

  1. For given two vertices s , t and a positive number k = O(1), how can I find the shortest path between s and t which contains at most k locked edges?

  2. For given two vertices s , t and a positive number k = O(1), how can I find the shortest path between s and t which contains exactly k locked edges?

I'm not sure how can I run Dijkstra algorithm on this graph to find the shortest path between the given vertices, and how can I transform the undirected graph, into an directed one.

1
algorithmdata-structuresgraphgraph-theorygraph-algorithm
Are paths allowed to contain cycles? Or are these simple paths? – templatetypedef
Treat locks as weight. If it is a locked edge it has a weight of say 1000. That should simplify it. – SH-
(By the way - nice Supaplex icon!) :-) – templatetypedef
@templatetypedef thanks man! :) – TomerGod

1 Answers

5
votes

You can solve both of your problems by taking k copies of the graph, say G_0, ..., G_k, and modifying each graph so that a locked edge vw in G_i turns into an edge from u in G_i to v in G_{i+1} and from v in G_i to u in G_{i+1}. Then you can do single-source shortest paths from your root in G_0. The second query is solved by reading off the distance to the target in G_k, while the first is solved by reading off the minimum distance in any G_i to the target.