这里是图
全部代码
#include<stdio.h> int main() { int inf = 999999;//表示两个点之间未相连 int e[20][20];邻接矩阵存储边 int dis[20];//储存起点到其余点的最短路径 int book[20];//表示点是否被遍历 int n, u, min; //n总点数,u标记点,min最短边 int count1 = 1,count2 = 1; char node[] = {"0ABCDEFGHIJKLMN"}; char start1,last1;//初位置点 printf("请输入初末位置点:\n"); scanf("%c %c",&start1,&last1); int start2,last2;//初末位置点序号,一共点 for(int i = 1;node[i]!='\0';i++) { if(node[i]==start1) start2 = i; if(node[i]==last1) last2 = i; n = i;//总点数 } printf("起始位置=%c,终点位置=%c。",node[start2],node[last2]); // scanf("%d %d", &n, &m);///n表示顶点个数,m表示边的条数 ///初始化 for (int i = 1; i <= n; i++)///这里创建的是一个邻接矩阵,n*n的矩阵 for (int j = 1; j <= n; j++) if (i == j) e[i][j] = 0; else e[i][j] = inf; //手动提前将图存入 e[1][2]=1,e[1][3]=1,e[1][4]=3; e[2][7]=2; e[3][5]=1; e[4][13]=3; e[5][6]=1; e[6][9]=2; e[7][10]=5; e[9][12]=3; e[10][12]=2; e[11][12]=2,e[11][14]=6; e[13][14]=5; //变成无向图 for(int i = 1;i<=n;i++) { for(int j = 1;j<=n;j++) { if(e[i][j] != inf) e[j][i] = e[i][j]; } } //测试输入的图是否正确 // for(int i = 1;i<=n;i++) // { // for(int j = 1;j<=n;j++) // { // if( e[i][j]!=inf ) // printf("e[%d][%d] = %d\t",i,j,e[i][j]); // } // } //初始化dis数组,这里要求的是起始顶点到其余各点的初始路程 for (int i = 1; i <= n; i++) { dis[i] = e[start2][i]; } //初始化book数组,这里面存的是已经被标记过的点 for (int i = 1; i <= n; i++) { book[i] = 0; } book[start2] = 1;///表示该点是已经被标记过的点 // path1[count1++]=start2; // path2[count2++]=start2; //核心代码 for (int i = 1; i <= n - 1; i++) { min = inf; for (int j = 1; j <= n; j++)///找到相邻点中未标记点中的最小值 { if (book[j] == 0 && dis[j]<min) { min = dis[j]; u = j; } } book[u] = 1; for (int k = 1; k <= n; k++)///找到相邻的结点 { if (e[u][k]<inf) { if (dis[k]>dis[u] + e[u][k]) //判断距离,核心思想 { dis[k] = dis[u] + e[u][k]; } } } } ///输出最终结果 for(int i = 1;i<n;i++) { // printf("%c->",node[path[i]]); } printf("\n点%c到点%c最短距离=%d ",node[start2],node[last2], dis[last2]); return 0; }