为什么我的 Dijkstra 算法的实现没有正常运行？

Question

我正在编写 Dijkstra 算法的实现来学习很酷的图形算法（这不是家庭作业，仅供参考）。我使用维基百科的 description 算法作为我的主要资源。

我测试了不同的遍历路径，得到了如下结果（(foo, bar)表示foo to bar）：

crashes:
    (e, f)
    (f, d)
    (c, a)
    (f, g)
incorrect:
    (a, c)
    (g, f)
working:
    (d, f)

我正在使用的图表如下所示：

       F - H
       |   |
A ---- B - C
|         /
|        /
E - G - D

通过跟踪从 E 到 F 的路径，我大致了解了我的代码失败的原因。另一个问题是我不知道如何使用我的其他方式来实现算法。这是从 E 到 F 的追踪：

在节点 E，我的邻居是 A 和 G。最短的暂定距离是 G，所以这是下一个当前节点。 G的邻居是E和D，但是E已经遍历过了，所以C是下一个。对于C，它的邻居D被遍历了，所以我们现在到达B（B和H是等距离的，但是它在C 的边列表）。这是我的问题所在：

A的暂定距离已经被E计算为2。由于从B到A的新暂定距离远大于仅仅2 , 它的距离保持在 2。对于F，它的距离设置为暂定距离，因为它被初始化为infinity。 A的距离较小，因此被选为下一个节点。 A的邻居只有E和B，它们已经被遍历过了，所以它周围的所有节点都已经被探索过了。变量 closest（见下面我的代码）被初始化为一个节点，除了 infinity 的 distance 之外没有其他填充字段，因此对于下一次迭代，它没有边，我遇到了分段错误。

我知道这就是我的代码中发生的事情，因为它的输出如下所示：

Current: e
New neighbor: a
New neighbor: g
g, closest, distance of 1
Current: g
New neighbor: d
d, closest, distance of 2
Current: d
New neighbor: c
c, closest, distance of 4
Current: c
New neighbor: b
New neighbor: h
b, closest, distance of 5
Current: b
New neighbor: a
New neighbor: f
a, closest, distance of 2
Current: a
?, closest, distance of 1000
Current: ?
Segmentation fault: 11

我实现这个算法哪里出错了？我已经尝试非常仔细地遵循维基百科的 6 步描述。他们的描述和我的唯一区别是我没有使用集合来跟踪已探索和未探索的节点（相反，数据保存在节点本身中）。请提供任何见解。

注意：我在 Mac 上使用 Clang 进行编译，没有优化 (-O0)。我注意到，通过更高的优化，我的程序会无限重复出现，然后又出现另一个分段错误，但我会优先考虑用我的算法解决核心问题，然后再处理它。

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>

#define infinity 1000

struct Node {
    unsigned char value;
    int visited, distance, edge_count;
    int* weights, weight_assign_index, freed;
    struct Node** edges;
};

typedef struct Node Node;

Node* init_node(const unsigned char value, const int edge_count) {
    Node* node = malloc(sizeof(Node));

    node -> value = value;
    node -> visited = 0;
    node -> distance = infinity;
    node -> edge_count = edge_count;

    node -> weights = malloc(edge_count * sizeof(int));
    node -> weight_assign_index = 0;
    node -> freed = 0;

    node -> edges = malloc(edge_count * sizeof(Node*));

    return node;
}

void assign_edges(Node* node, const int amount, ...) {
    va_list edges;
    va_start(edges, amount);

    for (int i = 0; i < amount; i++)
        node -> edges[i] = va_arg(edges, Node*);

    va_end(edges);
}

void assign_weight(Node* node_1, Node* node_2, const int weight) {
    for (int i = 0; i < node_1 -> edge_count; i++) {
        if (node_1 -> edges[i] == node_2) {
            node_1 -> weights[node_1 -> weight_assign_index++] = weight;
            node_2 -> weights[node_2 -> weight_assign_index++] = weight;
        }
    }
}

void deinit_graph(Node* node) {
    if (!node -> freed) {
        node -> freed = 1;
        free(node -> weights);
        for (int i = 0; i < node -> edge_count; i++)
            deinit_graph(node -> edges[i]);
        free(node -> edges);
    }
}

void dijkstra(Node* current, Node* goal) {
    Node local_closest;
    local_closest.distance = infinity;
    Node* closest = &local_closest;

    printf("Current: %c\n", current -> value);

    for (int i = 0; i < current -> edge_count; i++) {
        Node* neighbor = current -> edges[i];
        if (!neighbor -> visited) {
            printf("New neighbor: %c\n", neighbor -> value);
            const int tentative_distance = current -> distance + current -> weights[i];

            if (tentative_distance < neighbor -> distance)
                neighbor -> distance = tentative_distance;

            if (neighbor -> distance < closest -> distance)
                closest = neighbor;
        }
    }
    printf("%c, closest, distance of %d\n", closest -> value, closest -> distance);

    current -> visited = 1;
    if (closest == goal) printf("Shortest distance is %d\n", closest -> distance);
    else dijkstra(closest, goal);
}

int main() {
    Node
        *a = init_node('a', 2),
        *b = init_node('b', 3),
        *c = init_node('c', 3),
        *d = init_node('d', 2),
        *e = init_node('e', 2),
        *f = init_node('f', 2),
        *g = init_node('g', 2),
        *h = init_node('h', 2);

    assign_edges(a, 2, e, b);
    assign_edges(b, 3, a, f, c);
    assign_edges(c, 3, b, h, d);
    assign_edges(d, 2, c, g);
    assign_edges(e, 2, a, g);
    assign_edges(f, 2, b, h);
    assign_edges(g, 2, e, d);
    assign_edges(h, 2, f, c);

    assign_weight(a, e, 2);
    assign_weight(a, b, 4);
    assign_weight(b, c, 1);
    assign_weight(b, f, 1);
    assign_weight(f, h, 1);
    assign_weight(h, c, 1);
    assign_weight(c, d, 2);
    assign_weight(d, g, 1);
    assign_weight(g, e, 1);


    e -> distance = 0;
    dijkstra(e, f);
    deinit_graph(a);
}

Answer 1

再次阅读维基百科算法的第 6 步：

Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

这里的“select”的意思是“在整个图中所有未访问的节点之间”，而不仅仅是在当前节点的未访问的邻居之间，这是你的代码正在做的。因此，如果最小暂定距离的未访问节点不是当前节点的邻居，您的代码就会误入歧途。如果当前节点根本没有未访问的邻居（这是完全有可能的，无论是遇到像你遇到的情况，还是更简单的死胡同节点），你的代码荒谬地访问 local_closest 节点，它根本不在图中并且其边缘未初始化，自然会导致崩溃。

因此，您在访问 A 之前就偏离了正确的算法。当您完成访问 D 时，剩余未访问的节点是暂定距离 2 处的 A、暂定距离 4 处的 C 和暂定距离无穷大处的 B、F、H。所以根据算法，你接下来应该访问 A。但是你又访问了 C，因为你的代码错误地只将当前节点的邻居视为下一个要访问的节点的候选者。

坦率地说，我根本看不出递归算法在这里是如何工作的。您需要访问一些跟踪所有未访问节点的数据结构，以便您可以随时找到最小暂定距离的节点，即使它离您当前节点很远。你在节点本身上跟踪访问状态的想法有一个问题，因为你没有很好的方法来搜索它们，除非回到起始节点并做某种 DFS/BFS。这是 (1) 在您当前的实现中不可能的，因为对 dijkstra 的递归调用不再有指向起始节点的指针，并且 (2) 非常低效，因为每次访问都是 O(N)。

维基百科算法建议在此处使用集合是有充分理由的。而且我认为它更适合迭代而不是递归算法。

为什么我的 Dijkstra 算法的实现没有正常运行？

Why does my implementation of Dijkstra's algorithm not behave as it should?

c

graph

dijkstra

shortest-path

graph-traversal