本次代碼為實驗六:基于 Dijsktra 算法的最短路徑求解實現(xiàn)。本實驗的重點在于對于Dijsktra算法的理解。有關(guān)Dijsktra的資料可以參考有關(guān)博文：
圖論：Dijkstra算法——最詳細(xì)的分析，圖文并茂，一次看懂！-CSDN博客
以下附上實現(xiàn)代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-763704.html
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxE 5
#define MVNum 100
#define MaxInt 32767
typedef struct{
char vex[MVNum]; //頂點表
int arcs[MVNum][MVNum];//鄰接矩陣，權(quán)重為整數(shù)
int Vexnum;//頂點數(shù)
int arcnum; //邊數(shù)
}AMGraph;
//全局變量部分
int cunt=0; //為存儲矩陣計數(shù)
int store[MaxE][MVNum]; //存儲結(jié)果矩陣 ,每個結(jié)果數(shù)組的第一位位存最短路徑值，后面為路徑節(jié)點
int ismin[MVNum]; //記錄該幾點是否已為最小值
//函數(shù)定義部分
void Dijsktra(AMGraph *a,char s,char e);
void Init(AMGraph *a);
int Read(AMGraph *a);
void Cal(AMGraph *a);
void show(int a[]);
int getIndex(AMGraph *a,char c);
//函數(shù)部分
void Init(AMGraph *a){ //初始化圖和存儲數(shù)組
a->arcnum=0;
a->Vexnum=0;
for(int i=0;i<MVNum;i++){
for(int j=0;j<MVNum;j++){
a->arcs[i][j]=MaxInt;
}
}
for(int i=0;i<MVNum;i++){
a->vex[i] = 0;
store[cunt][i] = 0;
ismin[i] = 0;
}
}
int getIndex(AMGraph *a,char c){ //獲取節(jié)點在圖中的位置
int rs;
for(int i=0;i<a->Vexnum;i++){
if(c==a->vex[i])return i;
}
}
void show(int a[]){ //輸出數(shù)據(jù)
printf("\n[RES]:\n");
printf("最短距離:%d\n",a[0]); //第一位為數(shù)字，直接輸出
printf("最短路徑:%c",a[1]);
for(int i=2;i<MVNum;i++){ //后面皆為字符;
if(a[i] == 0){
break;
}
printf("->%c",a[i]);
}
}
void Dijsktra(AMGraph *a,char s,char e){
int min=0;//記錄每一趟的最小值以及該節(jié)點
char minv;
int *lgti = (int*)malloc(sizeof(int)*a->Vexnum); //該數(shù)組用于更新節(jié)點節(jié)點的最短路徑
char ** lgtc = (char**)malloc(sizeof(char*)*a->Vexnum); //該數(shù)組用于保存每個節(jié)點當(dāng)前最短路徑
for(int i=0;i<a->Vexnum;i++){ //初始化
lgtc[i]=(char*)malloc(sizeof(char)*a->Vexnum);
lgtc[i][0] = s;
for(int j=1;j<a->Vexnum;j++)lgtc[i][j]=0;
lgti[i] = MaxInt;
}
minv=s;
for(int i=0;i<a->Vexnum-1;i++){ //每次確定一個最小路徑，最多共需v-1趟完成
for(int j=0;j<a->Vexnum;j++){ //每趟對v個節(jié)點路徑進行更新
//printf("\n%c:new =%d,old =%d\n",a->vex[j],min+a->arcs[getIndex(a,minv)][j],lgti[j]);
if(min+a->arcs[getIndex(a,minv)][j]<lgti[j]){ //若更新節(jié)點值小于現(xiàn)有最小值，則更新為改值
lgti[j] = min+a->arcs[getIndex(a,minv)][j];
strcpy(lgtc[j],lgtc[getIndex(a,minv)]);
lgtc[j][strlen(lgtc[j])] = a->vex[j];
}
}
min = MaxInt;
printf("[TRV %d]:",cunt+1);
for(int j=0;j<a->Vexnum;j++){
if(lgti[j]<min&&ismin[j]==0){ //若小于min且未定為最小值，則記錄
min = lgti[j];
minv = a->vex[j];
}
}
printf("新增最小路徑: %c\n",minv);
if(minv==e){
printf("Success!\n");
store[cunt][0] = min;
for(int i=0;i<strlen(lgtc[getIndex(a,e)]);i++){
store[cunt][i+1]=(int)lgtc[getIndex(a,e)][i];
}
cunt++;
break;
}
ismin[getIndex(a,minv)]=1;
}
}
void Cal(AMGraph *a){ //計算結(jié)果，Dijsktra
char start,end;
getchar(); //結(jié)果存儲
printf("請輸入起始節(jié)點: ");
scanf(" %c %c",&start,&end);
Dijsktra(a,start,end);
}
int Read(AMGraph *a){ //讀取數(shù)據(jù)
int n,m,lgt;
char ca,cb;
printf("請輸入n,m:");
scanf("%d%d",&n,&m);
if(n==0&&m==0)return 1;
a->Vexnum = n;
a->arcnum =m;
printf("請輸入頂點:");
for(int i=0;i<n;i++){
scanf(" %c",&a->vex[i]); //儲存節(jié)點
}
getchar();
printf("請輸入邊： \n");
for(int i=0;i<m;i++){ //存儲邊
scanf(" %c %c %d",&ca,&cb,&lgt);
a->arcs[getIndex(a,ca)][getIndex(a,cb)]=lgt;
}
return 0;
}
int main(){
int flag=0; //記錄是否輸入停止
AMGraph *a = (AMGraph*)malloc(sizeof(AMGraph));
printf("多組數(shù)據(jù)，每組數(shù)據(jù)有 m+3 行。\n第一行為兩個整數(shù) n 和 m，分別代表城市個數(shù) n 和路徑條數(shù) m。\n第二行有 n 個字符，代表每個城市的名字。\n第三行到第m+2 行每行有兩個字符 a 和 b 和一個整數(shù) d，代表從城市 a 到城市 b 有一條距離為 d 的路。\n最后一行為兩個字符，代表待求最短路徑的城市起點和終點。\n當(dāng) n 和m 都等于 0 時，輸入結(jié)束");
while(1){
Init(a); //初始化圖
printf("\n =================| -FZC- |=============== \n\n");
flag = Read(a); //讀取信息
if(flag==1){
printf("\n =================| -FZC- |=============== \n\n");
printf("\nFOLLOWING OUTPUI:\n");
printf("共尋徑[%d]次\n",cunt);
for(int i=0;i<cunt;i++)show(store[i]);
break;
}
Cal(a); //計算距離并存儲結(jié)果
}
return 0;
} 以上代碼僅供參考，歡迎交流。文章來源地址http://www.zghlxwxcb.cn/news/detail-763704.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)實驗任務(wù)六 ：基于 Dijsktra 算法的最短路徑求解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
