algorithm - 如何在计算没有边的顶点时找到最短路径？

Question

我有一个来自 Graphs 的任务，我需要找到最短路径。

这不是正常的算法，因为您不必计算路径，您需要计算顶点。

规则就像通过特定顶点的成本是:

| P = costOfPathFromThePreviousVertex - costOfPathToTheNextVertex |

例如，当您有 Graph 时: A-> B-> C->

成本是

  A->B = 10 ;
  B->C = 15 ;

通过顶点 B 的成本为: P = | 10 - 15 |

假设根顶点和目标顶点的成本 = 0。

所以在上述情况下，从 A 经 B 到 C 的成本将为 5。

说起来容易，但我不知道当我有 x 个顶点时我需要实现哪种算法才能得到结果。我也在考虑 Dijkstra 的算法和 DFS，但在那种情况下它们是不正确的。

任何帮助将不胜感激。

Answer 1

我会添加一个连接到实际起点和终点的虚拟起点和终点顶点。

然后将您的图形变成 line graph每条边都有一个顶点，例如v1="A->B"和 v2="B->C"。

根据您的公式为新图中的边分配权重。

例如，连接 v1 和 v2 的边的权重为 |10-15|。

然后在这个折线图上使用 Dijkstra 算法找到 dummy 起始边和 dummy 结束边之间的最短路径。