在执行Dijkstra时可以确定跳数吗？

Question

感谢@trincot中的电码，我可以修改Dijkstra以获得给定源节点和目标节点之间的最短路径。此外，在执行Dijkstra以找到最短路径时，我试图计算跳数，当跳数超过预定义的Max_hop时，Dijkstra将被终止，但我失败了。

Hop被定义为(N1)，其中N是包含在最短路径中的顶点数。

当然，在找到最短路径后，我们可以很容易地计算出跳数。然而，在Dijkstra的路径搜索过程中，我们能计算出给定源与给定源之间的跳数吗？

from heapq import heappop, heappush
def dijkstra(adjList, source, sink):
    n = len(adjList)   
    parent = [None]*n  
    heap = [(0,source,0)]
    explored_node=[]
    hop_count = 0
    Max_hop = 8    
    while heap:
        distance, current, came_from = heappop(heap)
        if parent[current] is not None:  # skip if already visited
            continue
        parent[current] = came_from  # this also marks the node as visited
        if sink and current == sink:  # only correct place to have terminating condition
            # build path
            path = [current]

            while current != source:
                current = parent[current]
                path.append(current)
            path.reverse()
            hop_count -=1
            print("Hop count is ",hop_count)
            
            return 1, distance, path
        for (neighbor, cost) in adjList[current]:
            if parent[neighbor] is None:  # not yet visited
                heappush(heap, (distance + cost, neighbor,  current))
                hop_count = hop_count + 1
                if hop_count > Max_hop:
                    print("Terminate")
adjList =[

[],

[[2,3],[4,11],[5,5]],
[[1,3],[3,5],[5,11],[6,7]],
[[2,5],[6,3]],
[[1,11],[5,15],[7,9]],
[[1,5],[2,11],[6,3],[7,6],[8,3],[9,9]],
[[2,7],[3,3],[5,3],[9,10]],
[[4,9],[5,6],[8,1],[10,11],[11,8]],
[[5,3],[7,1],[9,9],[11,11]],
[[5,9],[6,10],[8,9],[11,3],[12,8]],
[[7,11],[13,7],[14,3]],
[[7,8],[8,11],[9,3],[12,8],[14,6]],
[[9,8],[11,8],[15,11]],
[[10,7],[15,3]],
[[10,3],[11,6],[15,9]],
[[12,11],[13,3],[14,9]],
]

flag, dist, path = dijkstra(adjList,1,15)

print("found shortest path {}, which has a distance of {}".format(path, dist))

adjList的图如下：(红线是从1到15的最短路径)

​

我知道这是不正确的，因为当Dijkstra迭代邻居时，我制作的hop_cout + 1代表已探索的节点数，而不是hop_count。

我认为，有两个重要问题需要解决。

1. 当确定parent_node和neighbor_node之间的最短距离时，hop_count可以被加1。但是，Dijkstra通过迭代邻居节点找到最短路径，存储最短距离的数组在路径搜索过程中逐渐更新。How to determine Dijkstra has already found the shortest distance between a parent_node and a neighbor_node?
2. 仅仅条件1是不够的，甚至我们可以知道Dijkstra何时找到了两个节点之间的最短距离，但是我们如何知道neighbor_node是否包含在给定源和目的地之间的最短路径中？

总之，如果我们想知道Dijkstra运行期间的当前跳数，则需要设置hop_count +1，当确定了从parent_node到neighbor_node的最短路径时，neighbor_node将被包含到从源到目标节点的最短路径。

为了更好地定义这个问题，如下图所示，红线是node 1和node 15之间的最短路径，最短路径是1 ->5 ->8 ->7 ->10 ->13 ->15。

1. 当探索node 2并且确定node 1和node 2之间的最短距离为3时，hop_count不能被添加1，因为node 2不包含在1到15之间的最短路径中。
2. 当探索node 5并且确定node 1和node 5之间的最短距离为5时，由于node 5包含在1到15之间的最短路径中，所以hop_count 应该添加1。

我的理解正确吗？我能听到你的想法吗？“在表演Dijkstra时，能确定跳数吗？”

Answer 1

由于堆将有表示长度不同的路径的节点，所以不能希望使用一个变量来计算跳数。您需要在放在堆中的元组中添加hop计数作为附加信息，因为它特定于每个单独的路径。

其次，您需要允许进一步扩展到同一节点的不同路径，因为其中一些路径可能由于跳限而退出，而另一些路径则可能停留在该限制范围内。因此，具体而言，当已经访问过的节点找到一条代价更高的路径，但跳数较少时，仍然应该考虑它。这意味着came_from现在不是一个好的结构(因为它只允许一条路径通过一个节点)。相反，我们可以使用堆元素中包含的链接列表(反向引用)。

注意:我还会将max_hop作为函数的参数：

from heapq import heappop, heappush

def dijkstra(adjList, source, sink, max_hop=8):  # make max_hop a parameter
    n = len(adjList)   
    least_hops = [n]*n  # Used for deciding whether to visit node via different path
    heap = [(0, 0, (source, None))]  # came_from is now a linked list: (a, (b, (c, None)))
    while heap:
        distance, hop_count, chain = heappop(heap)  # hop_count is part of tuple
        current = chain[0]
        if hop_count >= least_hops[current]:
            continue  # Cannot be an improvement
        least_hops[current] = hop_count
        if sink and current == sink:
            print("Hop count is ", hop_count)
            path = []
            while chain:
                current, chain = chain  # Unwind linked list
                path.append(current)
            return 1, distance, path[::-1]
        
        if hop_count >= max_hop:  # no recursion beyond max_hop
            print("Terminate")
            continue
        hop_count += 1  # Adjusted for next pushes unto heap
        for neighbor, cost in adjList[current]:
            heappush(heap, (distance + cost, hop_count, (neighbor, chain)))  # Prepend neighbor

至于你的另一个问题：

如何确定Dijkstra已经找到了parent_node和neighbor_node之间的最短距离？

我们不会立即确定这一点，并允许同一节点的多条路径共存。if循环中的for检测节点是否已经被访问过(和)--跳到它的次数不是一个改进:这意味着它已经在堆上获得了优先级，并且在主while循环的早期迭代中被从堆中提取出来，因此我们已经有了通往该节点的最短路径。此if阻止我们在堆中推送无用的“替代”路径:即使最短路径需要稍后被拒绝，因为它不能停留在跳限内，但是一个没有使用较少跳数的替代路径也不能希望保持在限制范围内，因此现在可以拒绝它。

Answer 2

这里有两个问题，一个是如何跟踪路径的长度，另一个是在超过最大路径长度时终止程序。两者的答案完全不同。

一方面，只要在算法完成后获得路径的长度，就可以计算最短路径有多少跳数(尽管它似乎不是您想要的)。其次，您还可以跟踪在任意迭代中从源到任何给定节点X所需的跳数，只需跟踪当前路径从s到顶点X的长度，并在松弛步骤中更新邻居的路径长度。@trincot答案很大程度上涵盖了这一点，它也提供了代码。

现在，在讨论程序终止部分之前，让我陈述三个有用的引理，它们是通过Dijkstra算法不变量的。

引理1:对于每个标记顶点，从源到该顶点的距离是最短路径。 引理2:对于每个未加标记的顶点，当前记录的距离是一条最短路径，仅考虑已经访问过的顶点。 引理3:如果最短的是s -> . -> u -> v，那么当你被访问时，当它的邻居距离更新时，距离d(s，v)将保持不变。

这些引理告诉我们：

1. 当节点X被标记为访问时: d(s，x)是极小的，路径s->x的长度将保持不变(引理1)。
2. 直到节点X被标记为已访问的d(s，x)，并且路径s->x的长度无论当前路径长度是多少，都是一个估计。这两个值都可能发生变化。(引理2)
3. 您不能保证长度为N的路径是最短路径，也不能保证最短路径具有长度<= N(引理3)

因此，如果您决定在从源到接收器的路径长度大于最大跳数时终止程序，则无法保证所获得的信息是最佳的。特别是，其中任何一种情况都可能发生在程序终止时：

• 路径长度为N，但另一条较短距离的路径为N。
• 路径长度为N，还有另一条较短长度和较短距离的路径。

如果您想在限制路径长度的同时获得从源到接收器的最短路径，则应该使用行李员-福特算法，它保证在每次迭代时，i所有路径的长度最多为i边，并且该路径在该约束下最短。

Answer 3

此代码使用dijkstra算法的prioirty队列。

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <vector>
#define limit 15

using namespace std;

int cost[20001];
vector<int> plist[20001];

const int MaxVal = -1;

vector< vector< pair<int, int> > > arr;

struct node {
    pair<int, int> info;
    vector<int> path;
};

bool operator < (node a, node b) {
    return a.info.first > b.info.first;
}

int main() {
    int i, j, k;
    int n, m;
    int s;
    int a, b, c;
    cin >> n >> m;
    cin >> s;
    //arr.reserve(n + 1);
    arr.resize(n + 1);

    for (i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        arr[a].push_back({ b, c });
    }

    for (i = 1; i <= n; i++) {
        cost[i] = MaxVal;
    }

    priority_queue<node, vector<node>> mh;
    mh.push(node{ { 0, s }, { } });
    while (mh.size() > 0) {
        int current = mh.top().info.second;
        int val = mh.top().info.first;
        auto path = mh.top().path;
        mh.pop();
        if (cost[current] != MaxVal) continue;//All path would be sorted in prioirty queue. And the path that got out late can't be the shorter path.
        cost[current] = val;
        path.push_back(current);
            if(path.size() > limit) {
                //limit exceeded!! 
                cout << "limitation exceeded!!";
                break;
            }
        plist[current] = path;
        for (auto it : arr[current]) {
            if (cost[it.first] != MaxVal) continue;
            mh.push({ { it.second + val, it.first }, path });
        }
    }

    for (i = 1; i <= n; i++) {
        cout << "path to " << i << " costs ";
        if (cost[i] == MaxVal) {
            cout << "INF\n";
        }
        else {
            cout << cost[i] << "\n";
        }
        for (auto p : plist[i]) {
            cout << p << " ";
        }
        cout << endl << endl;
    }   

    return 0;
}

//test case
15 55
1 //Starting Node Number
1 2 3
1 4 11
1 5 5
2 1 3
2 3 5
2 5 11
2 6 7
3 2 5
3 6 3
4 1 11
4 5 15
4 7 9
5 1 5
5 2 11
5 6 3
5 7 6
5 8 3
5 9 9
6 2 7
6 3 3
6 5 3
6 9 10
7 4 9
7 5 6
7 8 1
7 10 11
7 11 8
8 5 3
8 7 1
8 9 9
8 11 11
9 5 9
9 6 10
9 8 9
9 11 3
9 12 8
10 7 11
10 13 7
10 14 3
11 7 8
11 8 11
11 9 3
11 12 8
11 14 6
12 9 8
12 11 8
12 15 11
13 10 7
13 15 3
14 10 3
14 11 6
14 15 9
15 12 11
15 13 3
15 14 9

path to 1 costs 0
1

path to 2 costs 3
1 2

path to 3 costs 8
1 2 3

path to 4 costs 11
1 4

path to 5 costs 5
1 5

path to 6 costs 8
1 5 6

path to 7 costs 9
1 5 8 7

path to 8 costs 8
1 5 8

path to 9 costs 14
1 5 9

path to 10 costs 20
1 5 8 7 10

path to 11 costs 17
1 5 8 7 11

path to 12 costs 22
1 5 9 12

path to 13 costs 27
1 5 8 7 10 13

path to 14 costs 23
1 5 8 7 11 14

path to 15 costs 30
1 5 8 7 10 13 15