【数据结构—图】Dijkstra算法求解单源最短路径

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MaxSize 50

typedef struct ArcNode{
    int data;
    ArcNode *next;
};

struct VNode{
    char value;
    ArcNode *first;
};

struct AdGraph{
    VNode vertices[MaxSize];
    int arcnum;vexnum;
};

//Dijkstra算法
void Dijkstra(AdGraph G,int v,int *visited,int *dis,int *path){
    for(int i = 0;i < G.vexnum;i++){
        dis[i] = INF;
        visited[i] = 0;
        path[i] = -1;
    }
    dis[v] = 0;
    visited[v] = 1;
    ArcNode *p = G.vertices[v].first;
    while(p){
        dis[p->adjvex] = p->weight;
        path[p->adjvex] = v;
        p = p->next;
    }
    int min,minIndex;
    for(int i = 0;i <G.vexnum - 1;i++){
        min = INF;
        for(int j = 0;j < G.vexnum;j++){
            if(!visited[j] && dis[j] < min){
                min = dis[j];
                minIndex = j;
            }
        }
        visited[minIndex] = 1;
        ArcNode *p = G.verticed[minIndex].first;
        while(p){
            if(!visited[p->adjvex] && dis[p->adjvex] > dis[minIndex] + p->weight){
                dis[p->adjvex] = dis[minIndex] + p->weight;
                path[p->adjvex] = minIndex;
            }
            p = p->next;
        }
    }
}