dijkstra 算法在 C++ 中使用矩阵。这段代码有什么问题？

Question

#include <iostream>



int n, m, v1, v2, weight;

cin >> n >> m;
int** graph = new int*[n];
int* distance = new int[n];
int* s = new int[n];

for (int i = 0; i < n; ++i)
    graph[i] = new int[n];

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        graph[i][j] = INT_MAX;

for (int i = 0; i < m; ++i)
{
    cin >> v1 >> v2 >> weight;
    graph[v1][v2] = weight;
    graph[v2][v1] = weight;
}

for (int i = 0; i < n; ++i)
    distance[i] = INT_MAX;


for (int i = 0; i < n; ++i)
    distance[i] = graph[0][i];

for (int i = 0; i < n; ++i)
    s[i] = 0;

distance[0] = 0;

int min = INT_MAX;
int vertex = 0;

for (int j = 0; j < n-1; ++j){
    min = INT_MAX;

    for (int i = 0; i < n; ++i)
        if (s[i] == 0 && min >= distance[i])
        {
            vertex = i;
            min = distance[i];
        }

    s[vertex] = 1;
    cout << vertex << " ";
    for (int i = 0; i < n; ++i)
        if (distance[i]>distance[vertex] + graph[vertex][i])
            distance[i] = distance[vertex] + graph[vertex][i];



}
for (int i = 0; i < n; ++i)
    cout << distance[i] << " ";

cout << endl;

    return 0;

}

你好。我正在使用二维矩阵制作 Dijkstra 算法。但这段代码不起作用。我不知道为什么！你能解决我的问题吗？？我想输出图形的所有距离。但输出看起来像数组点垃圾值，如 -2345 ... 你能帮帮我吗？？

Answer 1

这个循环有一些问题：

for (int i = 0; i < n; ++i)
        if (distance[i]>distance[vertex] + graph[vertex][i])
            distance[i] = distance[vertex] + graph[vertex][i];

应该改成爆破代码：

for (int i = 0; i < n; ++i)
        if (s[i] == 0 && graph[vertex][i] != INT_MAX && distance[i]>distance[vertex] + graph[vertex][i])
            distance[i] = distance[vertex] + graph[vertex][i];

因为如果graph[vertex][i] == INT_MAX，distance[vertex] + graph[vertex][i]的和就溢出了。另一个问题是之前不应该标记顶点i。

dijkstra 算法在 C++ 中使用矩阵。这段代码有什么问题？

dijkstra's algorithm using matrix in c++. what's wrong in this code?

c++

algorithm

dijkstra