#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