迪杰斯特拉算法（Dijkstra）

#include “stdio.h“
#define MAXSIZE 20
#define INFINITY 9999

typedef struct {
    char vexs[MAXSIZE];//vertices infoemation
    int arcs[MAXSIZE][MAXSIZE];
    int arcNum vexNum;
}MGraph;

void dijkstra（MGraph G int v） {
    int dist[MAXSIZE];              //dist[i]:源点到点 i 的路径长度
    int path[MAXSIZE][MAXSIZE];     //path[i][]:源点到点 i 经过的顶点j下标集合
    int i j k m min n flag;
    
    for（i=0; i        for（j=0; j            path[i][j] = -1;
        }
    }
    
    for（i=0; i        dist[i]=G.arcs[v][i];                //dist[]初始状态为arcs[][]第v行
        if（dist[i]!=0 && dist[i]!=INFINITY） {//与源点 v 有关系的顶点第一个经过的点为 v
            path[i][0]=v;
        }
    }
    n=0;        //打印最短路径时对应第%d条
    flag=1;     //循环结束标志
    
    //从小到大找最短路径
    while（flag） {
        k=0;                //每一轮循环中要选择的最短路径长度对应的顶点下标
        min=INFINITY;       //每一轮循环中要选择的最短路径长度
        
        for（j=0; j            if（dist[j]!=0 && dist[j]                k=j;
                min=dist[j];
            }
        }
        printf（“第%d条最短路径长度为%d--（“ ++n min）;     //显示最短路径
        for（j=0; j            if（path[k][j]!=-1） {                         //打印从源点到最短路径顶点经过的顶点
                printf（“%d“ path[k][j]）;
            }
        }
        printf（“%d）\n“ k）;
        for（j=0; j            if（j!=k && G.arcs[k][j]!=INFINITY） {
                if（dist[k]+G.arcs[k][j]                    dist[j]=dist[k]+G.arcs[k][j];
                    for（m=0; m