dijkstra - 当我尝试在 Dijkstra 算法中添加父数组时如何解决这个错误的访问问题

Question

#include<limits.h>
#include<stdio.h>

using namespace std;
#define V 9
 int parent[V];
///?we use a boolean array sptSet[] to represent the set of vertices included in SPT.
//?if a value sptSet[v] is true,then vertex v is included.
//a utility function to find the vertex with minimum distance value
//from the set of vertices not yet included in shortest path tree

int minDistance(int dist[],bool sptSet[])
{
    int min=INT_MAX,min_index;
    for(int v=0;v<V;v++){
        if(sptSet[v]==false&&dist[v]<=min){
            min=dist[v],min_index=v;
        }
    }
    return min_index;
}
int printMST(int parent[V],int graph[V][V],int stop);//function prototype
//a utility function to print the constructed distance array
void printSolution(int dist[V],int src,int parent[V]){
    printf("Vertex \t\t Distance from source\n");
    for(int i=0;i<V;i++){
        printf("%d \t\t %d\n",i,dist[i]);
        //?Now we also want to show how the path from source got here.
        int temp=i;
        while(parent[temp]!=src) {
            printf("\n %d <- ",parent[temp]);
            temp=parent[temp];
    
    }
    printf(" <-%d",src);//the final stop is the source,where it originated.
}
}
int printMST(int parent[],int graph[V][V],int stop){
    for(int i=1;i<=stop;i++)
        printf("\n%d -%d \t%d\n ",parent[i],i,graph[i][parent[i]]);
}
//!We can create a parent array,update the parent array when distance is updated
//!and use it to show the shortest path from source to different vertices
void dijkstra(int graph[V][V],int src)
{
    int dist[V];//the output array.it would hold the shortest distince from src to i
   
    bool sptSet[V];
    for(int i=0;i<V;i++)
        dist[i]=INT_MAX,sptSet[i]=false;
        //distance of src from itself is always zero
        //&find shortest path for all vertices
        dist[src]=0;
        parent[0]=-1;
        for(int count=0;count<V-1;count++){
            int u=minDistance(dist,sptSet);
            //?mark the picked vertex as processed
            sptSet[u]=true;
            //?updates dist value of the adjacent vertices of the picked vertex
            for(int v=0;v<V;v++)
                //!update dist[v] only if it is not in SPT,there is an edge from u to v,

                //!and total weight of path from src to v through u is smaller than current value of dist[v]
                if(!sptSet[v]&&graph[u][v]&&dist[u]!=INT_MAX&&dist[u]+graph[u][v]<dist[v]){
                dist[v]=dist[u]+graph[u][v];
                parent[v]=u;}
            }
            printSolution(dist,src,parent);//?a little adjustment

        }

// driver program to test above function
int main()
{
    /* Let us create the example graph discussed above */
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
 
    dijkstra(graph, 0);
 
    return 0;

}

我正在尝试向我的 Dijkstra 程序添加一个父数组，以便打印从源到每个顶点的路径。在我添加数组之前，我的程序运行良好，它向我显示 BAD_ACCESS 错误，但我似乎无法找到问题。错误的访问错误出现在我写“while（parent [temp]！= src）”的那一行。我尝试调试它但仍然无法理解为什么会出现错误。有人可以解释一下吗？

标签： dijkstra