#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]:源點(diǎn)到點(diǎn)?i?的路徑長(zhǎng)度
????int?path[MAXSIZE][MAXSIZE];?????//path[i][]:源點(diǎn)到點(diǎn)?i?經(jīng)過(guò)的頂點(diǎn)j下標(biāo)集合
????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[]初始狀態(tài)為arcs[][]第v行
????????if（dist[i]!=0?&&?dist[i]!=INFINITY）?{//與源點(diǎn)?v?有關(guān)系的頂點(diǎn)第一個(gè)經(jīng)過(guò)的點(diǎn)為?v
????????????path[i][0]=v;
????????}
????}
????n=0;????????//打印最短路徑時(shí)對(duì)應(yīng)第%d條
????flag=1;?????//循環(huán)結(jié)束標(biāo)志
????
????//從小到大找最短路徑
????while（flag）?{
????????k=0;????????????????//每一輪循環(huán)中要選擇的最短路徑長(zhǎng)度對(duì)應(yīng)的頂點(diǎn)下標(biāo)
????????min=INFINITY;???????//每一輪循環(huán)中要選擇的最短路徑長(zhǎng)度
????????
????????for（j=0;?j????????????if（dist[j]!=0?&&?dist[j]????????????????k=j;
????????????????min=dist[j];
????????????}
????????}
????????printf（“第%d條最短路徑長(zhǎng)度為%d--（“?++n?min）;?????//顯示最短路徑
????????for（j=0;?j????????????if（path[k][j]!=-1）?{?????????????????????????//打印從源點(diǎn)到最短路徑頂點(diǎn)經(jīng)過(guò)的頂點(diǎn)
????????????????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