任務描述
本關任務：編程實現求圖的最短路徑
相關知識
最短路徑的Dijkstra算法：
求最短路徑就是求圖中的每一個點到圖中某一個給定點（認為編號為0的點）的最短距離。
具體算法就是初始有一個舊圖，一個新圖。開始時舊圖中有所有的結點，新圖中初始為只有一個結點（源點，路徑的源頭）。整個算法就是不停的從舊圖中往新圖中添加點，直到所有的點都添加到新圖中為止。
編程要求
根據提示，在右側編輯器補充代碼，計算并輸出圖的最短路徑
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：按照指導書上圖的數據進行輸入
預期輸出：
(1^5) (2^3) (4^2)
(2^2) (3^6)
(1^1) (3^2)
(1^6) (2^10) (3^4)
0@0,1@4,2@3,3@5,4@2

#include <stdio.h> #include <stdlib.h>char infomation[20]; //輸入圖 //1 5 2 3 4 2: //3 6 2 2: //3 2 1 1: //: //1 6 2 10 3 4:typedef struct{int length;//最短路徑長度int prevex;//從V0到Vi的最短路徑上Vi的前驅節點 }Path;Path *dist;int main(int argc, const char * argv[]) {int number = 5;int arcs[5][5]={{0,5,3,65535,2},{65535,0,2,6,65535},{65535,1,0,2,65535},{65535,65535,65535,0,65535},{65535,6,10,4,0}};dist = (Path*)malloc(sizeof(Path)*number);for(int i=0;i<number;i++){for(int j=0;j<number;j++){if(arcs[i][j]!=0&&arcs[i][j]!=65535){printf("(%d^%d)",j,arcs[i][j]);if(i==0&&j==4)printf(" ");for(int k=j+1;k<number;k++)if(arcs[i][k]!=0&&arcs[i][k]!=65535){printf(" ");break;}}}printf("\n");}//初始化指定頂點V0到V-U中各頂點的距離int i;dist[0].length=0;dist[0].prevex=0;arcs[0][0] = 1;for(i=1;i<number;i++){dist[i].length = arcs[0][i];if(dist[i].length!=65535)dist[i].prevex = 0;else dist[i].prevex = -1;}int j,mv;int min;for(i=1;i<number;++i){min = 65535;mv=0;for(j=1;j<number;++j)if(arcs[j][j]==0&&dist[j].length<min){mv = j;min=dist[j].length;}if(mv==0)break;arcs[mv][mv]=1;for(j=1;j<number;j++){if(arcs[j][j]==0&&dist[j].length>dist[mv].length+arcs[mv][j]){dist[j].prevex = mv;dist[j].length = dist[mv].length + arcs[mv][j];}}}for(i = 0;i<number-1;i++)printf("%d@%d,",i,dist[i].length);printf("%d@%d",i,dist[i].length);return 0; }

如果是寫實驗報告，可以用下面的代碼

#include <stdio.h> #include <stdlib.h>char infomation[20]; //輸入數據 5 //1 5 2 3 4 2: //3 6 2 2: //3 2 1 1: //: //1 6 2 10 3 4:typedef struct{int length;//最短路徑長度int prevex;//從V0到Vi的最短路徑上Vi的前驅節點 }Path;Path *dist;int main(int argc, const char * argv[]) {int number;printf("Enter a network. The minimal weights of paths from vertex 0 to other vertices\n");printf("How many vertices in the digraph (between 1 and 10)?");scanf("%d",&number);int arcs[number][number];dist = (Path*)malloc(sizeof(Path)*number);for(int i = 0;i<number;i++)for (int j=0; j<number ; j++)arcs[i][j]=0;printf("For each vertex, give the vertices to which it points.\nand the corresponding directed edge weight.\nType the pairs of numbers (terminated by a : for each vertex), separated by blanks.\n");for(int i=0;i<number;i++){printf("Vertex %d : ",i);fflush(stdin);fgets(infomation,20,stdin);int flag = 0;char temp='0';for(int j = 0;j<20;j++){if(infomation[j]==' ')continue;else if(infomation[j]==':')break;if(flag==0){temp = infomation[j];flag = 1;}else if(flag==1){arcs[i][temp-'0'] = infomation[j]-'0';if(infomation[j+1]!=' '&&infomation[j+1]!=':'){arcs[i][temp-'0']*=10;flag=3;continue;}flag=0;}else if(flag==3){flag=0;continue;}}for(int j = 0;j<20;j++) infomation[j] = '0';}for(int i = 0;i<number;i++){for (int j=0; j<number ; j++)if(i==j)arcs[i][j]=0;else if(arcs[i][j]==0)arcs[i][j]=65535;}printf("\nYou entered the graph:\n\n");for(int i=0;i<number;i++){printf("Vertex %d : ",i);for(int j=0;j<number;j++){if(arcs[i][j]!=0&&arcs[i][j]!=65535){printf("<%d^%d> ",j,arcs[i][j]);}}printf("\n");}//初始化指定頂點V0到V-U中各頂點的距離int i;dist[0].length=0;dist[0].prevex=0;arcs[0][0] = 1;for(i=1;i<number;i++){dist[i].length = arcs[0][i];if(dist[i].length!=65535)dist[i].prevex = 0;else dist[i].prevex = -1;}int j,mv;int min;for(i=1;i<number;++i){min = 65535;mv=0;for(j=1;j<number;++j)if(arcs[j][j]==0&&dist[j].length<min){mv = j;min=dist[j].length;}if(mv==0)break;arcs[mv][mv]=1;for(j=1;j<number;j++){if(arcs[j][j]==0&&dist[j].length>dist[mv].length+arcs[mv][j]){dist[j].prevex = mv;dist[j].length = dist[mv].length + arcs[mv][j];}}}printf("The minimal distances from vertex O to the other vertices are as follows:\n");for(i = 0;i<number;i++)printf("%d@%d, ",i,dist[i].length);printf("\n");return 0; }

不得不說，學校出的頭歌題目和實驗報告都有點問題，已經向老師反饋了

總結

以上是生活随笔為你收集整理的数据结构实验头歌 第1关：求图的最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。