Dijkstra 寻路

Question

我知道有很多问题是基于这个算法的。我是初学者，我被分配了寻路任务。我写了一些代码来找到两个节点之间的最短路径。在我的代码中，当我将 Node 设置为 0 时，它工作正常，但在其他节点上却不行。有什么问题吗？？

#include<iostream>
using namespace std;

int main(){
    int matrix[5][5];
    int visited[5];
    int distance[5];
    int min , nextnode=0;

    for(int i=0;i<5;i++){
        visited[i]=0;
        for(int j=0;j<5;j++){
            cin>>matrix[i][j];
            if(matrix[i][j] == 0)
                matrix[i][j] = 999;     
        }   
    }
    int inNode,traceBack[5],pathNode;
    cout<<"Enter Initial Node: ";
    cin>>inNode;
    cout<<"Enter Path Node: ";
    cin>>pathNode;
    distance[inNode] = 0;
    visited[inNode] =1;
    for(int i=0 ; i< 5 ; i++){
        distance[i]=matrix[inNode][i];

    }

    for(int i=0;i<5;i++){
        min=999;
        for(int j=0;j<5;j++){
            if(min>distance[j] && visited[j] != 1){
                min=distance[j];
                nextnode=j;
            }

        }
        visited[nextnode] = 1;
        for(int c=0;c<5;c++){
            if(visited[c]!=1){
                if(min+matrix[nextnode][c] < distance[c]){
                    distance[c] = min + matrix[nextnode][c];
                    traceBack[c] = nextnode;                    
                }
            }
        }
    }

    //  cout<<"->"<<traceBack[i];
    int j;
    cout<<"Path = "<<pathNode;
    j=pathNode;
    do{
        j=traceBack[j];
        cout<<"<-"<<j;
    }while(j!=inNode);  
    return 0;
}

Answer 1

您不更新 traceBack 可从 inNode 到达的节点，我建议您在初始化距离时执行此操作，

for(int i=0 ; i< 5 ; i++){
    distance[i]=matrix[inNode][i];
    traceBack[i] = inNode;
}

如果您有其他问题，请告诉我们。这就是您的算法终止的原因，但是当它尝试读取路径时，它会出现分段错误。

Dijkstra 寻路

Dijsktra Path Finding

c++

algorithm

dijkstra