for(i=1;i<N;i++) { Min=65535; for(j=0;j<N;j++) { if(!set[j]&&dis[j]<Min) { k=j; Min=dis[j]; } } set[k]=1; for(j=0;j<N;j++) { if(!set[j]&&(Min+arc[k][j]<dis[j])) dis[j]=Min+arc[k][j]; } }
const int N=9,INF=65535; int vexs[N]; int arc[N][N]; void init() { //初始化图 for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { arc[i][j] =INF; } } arc[0][1]=1; arc[0][2]=5; arc[1][2]=3; arc[1][3]=7; arc[1][4]=5; arc[2][4]=1; arc[2][5]=7; arc[3][4]=2; arc[3][6]=3; arc[4][5]=3; arc[4][6]=6; arc[4][7]=9; arc[5][7]=5; arc[6][7]=2; arc[6][8]=7; arc[7][8]=4; for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { arc[j][i] =arc[i][j]; } } for(int i=0;i<N;i++) vexs[i]=i; }
//初始化(这里以V0点开始) for(i=0;i<N;i++) { set[i]=0; dis[i]=arc[0][i]; } dis[0]=0; set[0]=1;
#include<stdio.h> const int N=9,INF=65535; int vexs[N]; int arc[N][N]; void init() { //初始化图 for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { arc[i][j] =INF; } } arc[0][1]=1; arc[0][2]=5; arc[1][2]=3; arc[1][3]=7; arc[1][4]=5; arc[2][4]=1; arc[2][5]=7; arc[3][4]=2; arc[3][6]=3; arc[4][5]=3; arc[4][6]=6; arc[4][7]=9; arc[5][7]=5; arc[6][7]=2; arc[6][8]=7; arc[7][8]=4; for(int i = 0; i < N; i++) { for(int j = i; j < N; j++) { arc[j][i] =arc[i][j]; } } for(int i=0;i<N;i++) vexs[i]=i; } int main() { init(); int i,j,k,Min; int set[N],dis[N]; //初始化(这里以V0点开始) for(i=0;i<N;i++) { set[i]=0; dis[i]=arc[0][i]; } dis[0]=0; set[0]=1; //主循环 for(i=1;i<N;i++) { Min=65535; //把距离v1,v2,v3,....最近的点找出来 for(j=0;j<N;j++) { if(!set[j]&&dis[j]<Min) { k=j; Min=dis[j]; } } set[k]=1; //根据最新找到的最短路径,更新v0点到各节点的最短距离 for(j=0;j<N;j++) { if(!set[j]&&(Min+arc[k][j]<dis[j])) dis[j]=Min+arc[k][j]; } } //输出结果 for(int i=1;i<N;i++) printf("%d ",dis[i]); }
原文:http://blog.csdn.net/u013011841/article/details/38539117