'Finding the shortest path with only passing specific edge less or equal to one time in Graph

Given a undirected graph that it has ordinary edges and specific edges, our goal is to find the sum of the shortest path's weight between two vertices(start vertex to end vertex) with only walk through specific edge equal or less than one time. In other words, there are multiple specific edges, and only at most one of them can be used.

This is a problem that I faced in my Data-Structure homework, and I stuck at the first step of the way to storage the weights of the edge in Graph. Because there are two kinds of edge in Graph, I have no idea that how to solve this problem.

I know that I can obtain the shortest path by using Dijkstra’s Algorithm, but during the process, how can I modify the Algorithm to meet the requirement of the restriction?

Thanks a lot for answering my question!

algorithmdata-structuresgraphshortest-pathdijkstra


Solution 1:[1]

The solution is to duplicate the graph as follows:

  • Duplicate the vertices, such that for each original vertex A, you have an A and an A'.

  • If in the original graph there is a normal edge between A and B, then in the new graph, place an edge between A and B and also between A' and B'

  • If in the original graph there is a specific edge between A and B, then in the new graph place a (directed) edge from A to B' (not the inverse!) and from B to A' (again: not the inverse!). These edges should be directed.

If now the task was to find the shortest path between S and D, then solve in the new graph the problem of finding the shortest path between S and D or S and D', which ever is shortest. You can use a standard implementation of Dijkstra's algorithm for that, starting in S and ending when you find either D or D'.

Solution 2:[2]

Given n specific edges run Dijkstra's search n times.
On each run, one of the n nodes (let call it node i) should be set to its real weight and all other n-1 nodes to an infinite value. At the end of each run store the shortest path and step i
At the end of all runs select from the stored paths the shortest one.

set all n edges weight to infinity 
for i=0;  i < n  ; i++ {
   set edge i to it real weight 
   run run  Dijkstra's search 
   store path 
   set all n edges weight to infinity 
}

select the shortest path from the stored paths.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2

Related Questions