在Graph中找到仅通过特定边少于或等于一次的最短路径

Question

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.

这是我在Data-Structure作业中遇到的问题，我卡在了第一步将边的权重存储在Graph中。因为Graph中有两种边，不知道怎么解决这个问题。

我知道用Dijkstra算法可以得到最短路径，但是在这个过程中，如何修改算法来满足限制的要求？

非常感谢您回答我的问题！

Answer 1

解决方案是按如下方式复制图形：

复制顶点，这样对于每个原始顶点 A，您都有一个 A 和一个 A'。
如果原图中A和B之间有一条正常的边，那么在新图中，在A和B之间以及A'和B'之间也有一条边
如果在原始图中 A 和 B 之间有一条特定边，则在新图中放置一条从 A 到 B'（不是逆向！）和从 B 的（有向）边到 A'（再次：不是相反！）。这些边应该是定向的。

如果现在的任务是寻找S和D之间的最短路径，那么在新图中解决寻找S和D之间的最短路径的问题或 S和D'，这是最短的。您可以为此使用 Dijkstra 算法的标准实现，从 S 开始到找到 D 或 D' 时结束。

Answer 2

给定 n 个特定边运行 Dijkstra 的搜索 n 次。
在每个运行上，其中一个 n 节点（我们称之为节点 i）应设置为其实际权重，而所有其他 n-1 节点应设置为无限值。在每个运行的末尾存储最短路径和步骤i
在所有运行s select 存储路径的末尾，最短的路径。

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.

在Graph中找到仅通过特定边少于或等于一次的最短路径

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

algorithm

data-structures

graph

shortest-path

dijkstra