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 require of the restriction?

Thanks a lot for answering my question!

CodePudding user response：

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'.