c++ - dijkstra 算法打印路径会跳过一些数字并且不适用于某些数字

Question

当 iam 打印路径时，如果起始数字是 2、4、6，它工作正常，如果它是 5，它什么也不打印，如果它的 1,3 它不打印第一个数字，例如
start:2
end:3
path: 2 6 5 3
开始：5
结束：3
路径：无
开始：3
结束：5
路径：4,5

点之间的距离工作得很好，我不明白为什么有些路径打印正确而其他路径打印不正确。

#include<iostream>
#include<fstream>
#include<climits>     /*Used for INT_MAX*/
using namespace std;
#define V 6      /*It is the total no of verteices in the graph*/
int minimumDist(int dist[], bool Dset[])   /*A method to find the vertex with minimum distance which is not yet included in Dset*/
{
    int min=INT_MAX,index;                 /*initialize min with the maximum possible value as infinity does not exist */
    for(int v=0;v<V;v++)
    {
        if(Dset[v]==false && dist[v]<=min)
        {
            min=dist[v];
            index=v;
        }
    }
    return index;
}
void printPath(int parent[], int j)
{
    // Base Case : If j is source
    if (parent[j] == -1)
    {
        return;
    }
    printPath(parent, parent[j]);
    printf("%d ", j+1);//+1 kad kazkas panasiau i veikima atrodytu
}
void dijkstra(int graph[V][V],int src,int n) /*Method to implement shortest path algorithm*/
{
    int dist[V];
    bool Dset[V];
    int parent[V];
    for(int i=0;i<V;i++)                    /*Initialize distance of all the vertex to INFINITY and Dset as false*/
    {
        parent[0] = -1;
        dist[i]=INT_MAX;
        Dset[i]=false;
    }
    dist[src]=0;                                   /*Initialize the distance of the source vertec to zero*/
    for(int c=0;c<V;c++)
    {
        int u=minimumDist(dist,Dset);              /*u is any vertex that is not yet included in Dset and has minimum distance*/
        Dset[u]=true;                              /*If the vertex with minimum distance found include it to Dset*/
        for(int v=0;v<V;v++)
        /*Update dist[v] if not in Dset and their is a path from src to v through u that has distance minimum than current value of dist[v]*/
        {
            if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v])
            {parent[v] = u;
            dist[v]=dist[u]+graph[u][v];}
        }
    }
    /*will print the vertex with their distance from the source to the console */
    if(dist[n-1]<999)
        {cout<<"atstumas nuo "<<src+1<<" iki "<<n<<" yra = "<<dist[n-1]<<endl;
        printPath(parent, n-1);}
        else
        cout<<"kelio i pabaigos taska nera"<<endl;
}
int main()
{
    int start,ending;
    cout<<"iveskite pradzia"<<endl;
    cin>>start;
    cout<<"iveskite pabaiga"<<endl;
    cin>>ending;

    int graph[V][V]={
    { 0,70,50,0,100,0 },
    { 0,0,0,35,0,20 },
    { 0,60,0,15,0,0 },
    { 0,0,0,0,30,45 },
    { 0,0,20,0,0,0 },
    { 0,0,0,0,4,0}};
    dijkstra(graph,start-1,ending);
    return 0;
}

标签： c++dijkstra