在Dijkstra算法中找到正加权图中的最短路径时，是否存在路线A-> B与路线B-> A不相等的情况？ （A和B是图形上的顶点）。你能举个例子吗？
如果图形不是定向的，则从A到B（S_{ab}）的最短路径的集合与从B到A（S_{ba}）的最短路径的集合相同。您可以通过矛盾证明这一点。
假设不是。因此，至少有一条从P到B的路径A不在S_{ab}中。由于图形不是有向图，因此从A到B的路径相同。如果路径的长度大于S_{ab}中的所有路径，那么它不是从B到A的最短路径，因为您可以从B到A并以最短路径中的一个路径返回在S_{ab}中。
[此外，如果P的长度小于S_{ab}中路径的长度，那么我们可以以小于A中所有路径的成本从B转到S_{ab}。因此，根据集合的定义，P必须位于S_{ab}中。但是，它与假设相矛盾。因此，这是不可能的。