//Dijkstra

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

define MaxVex 100

typedef char VexType;
typedef int EdgeType;
typedef struct{
VexType node[MaxVex];
EdgeType edges[MaxVex][MaxVex];
int vexnum,edgenum;
}AdjMatrix;
//邻接矩阵定义

typedef struct {
int v0;
int v1;
int weight;
}Edge;

define MaxInt 50

int dist[MaxVex];//dist[i]代表到达结点i的最短路径长度
int path[MaxVex];//到达i最短路径中，i结点的上一个结点
int isjoin[MaxVex];//0就代表当前结点没有找到最短路径
void Dijkstra(AdjMatrix G,int v){
for(int i=1;i<=G.vexnum;i){
dist[i]=G.edges[v][i];
isjoin[i]=0;
if(dist[i]<MaxInt){
path[i]=v;
}
else path[i]=-1;
}
dist[v]=0;
isjoin[v]=1;
for(int i=1;i<=G.vexnum-1;i){//共经历n-1轮
int u=1,min=MaxInt;
for(int j=1;j<=G.vexnum;j)
{
if(isjoin[j]==0&&dist[j]<min){
u=j;
min=dist[j];
}
}
if(min==MaxInt) return;//此时剩下的点都无法到达，距离为无穷
printf(“%d-%d:%d\n”,v,u,min);
isjoin[u]=1;
for(int j=1;j<=G.vexnum;j){
if(isjoin[j]==0&&dist[u]+G.edges[u][j]<dist[j]){
dist[j]=dist[u]+G.edges[u][j];
path[j]=u;
}
}
}
}

void create(AdjMatrix &G,Edge data[],int n){
for(int i=1;i<=MaxVex-1;i){
for(int j=1;j<=MaxVex-1;j)
G.edges[i][j]=MaxInt;
}
for(int i=1;i<=G.vexnum;i) G.edges[i][i]=0;
for(int i=0;i<n;i){
G.edges[data[i].v0][data[i].v1]=data[i].weight;
G.edges[data[i].v1][data[i].v0]=data[i].weight;
}
}

int main(){
AdjMatrix G;
G.vexnum=7;
G.edgenum=12;
Edge data[]={{1,2,23},{1,7,36},{1,6,28},{2,7,1},{2,3,20},
{3,7,4},{3,4,15},{4,7,9},{5,4,3},{5,7,16},{5,6,17},{6,7,25}
};
AdjMatrix &M=G;
create(M,data,12);
// for(int i=1;i<=G.vexnum;i){
// for(int j=1;j<=G.vexnum;j)
// cout<<setw(3)<<G.edges[i][j]<<’ ‘;
// cout<<endl;
// }
Dijkstra(G,1);
for(int i=1;i<=G.vexnum;i++) cout<<dist[i]<<’ ‘;
cout<<endl;
int i=5;
while(path[i]!=1){
cout<<path[i]<<’ ‘;
i=path[i];
}
}