實(shí)驗(yàn)六 基于Dijsktra算法的最短路徑求解
一、實(shí)驗(yàn)?zāi)康?br> 1.掌握?qǐng)D的鄰接矩陣表示法，掌握采用鄰接矩陣表示法創(chuàng)建圖的算法。
2.掌握求解最短路徑的 Dijsktra 算法。
二、實(shí)驗(yàn)內(nèi)容
一張地圖包括 n 個(gè)城市，假設(shè)城市間有 m 條路徑(有向圖)，每條路徑的長(zhǎng)度
已知。給定地圖的一個(gè)起點(diǎn)城市和終點(diǎn)城市，利用 Dijsktra 算法求出起點(diǎn)到終
點(diǎn)之間的最短路徑
三、實(shí)驗(yàn)實(shí)習(xí)設(shè)備及開(kāi)發(fā)環(huán)境
Visual studio 2022
四．實(shí)驗(yàn)實(shí)習(xí)過(guò)程步驟（注意是主要關(guān)鍵步驟，不是所有步驟，適當(dāng)文字+截圖說(shuō)明）
Function1：初始化圖，將結(jié)構(gòu)體里面的節(jié)點(diǎn)數(shù)和邊數(shù)都輸入，然后根據(jù)路徑間的關(guān)系，對(duì)鄰接矩陣進(jìn)行填充，如果在兩個(gè)節(jié)點(diǎn)間有路徑，則在對(duì)應(yīng)的鄰接矩陣中修改權(quán)重（首先要將鄰接矩陣初始化，就是將所有的全部變成無(wú)窮大）。因?yàn)轭}目中是有向圖，所以不需要將對(duì)稱(chēng)的節(jié)點(diǎn)也修改，如果是無(wú)向圖，就需要將對(duì)稱(chēng)的也修改。
Funtion2：Dijkstra算法。從起點(diǎn)開(kāi)始，建立一個(gè)數(shù)組來(lái)存儲(chǔ)節(jié)點(diǎn)是否訪問(wèn)，一個(gè)數(shù)據(jù)記錄節(jié)點(diǎn)離各點(diǎn)的距離，還有一個(gè)來(lái)記錄最短路徑。首先，從起點(diǎn)開(kāi)始，將起點(diǎn)下標(biāo)加入到最短路徑數(shù)組里面，到個(gè)點(diǎn)距離首先設(shè)置為0，變?yōu)橐呀?jīng)訪問(wèn)。然后依次訪問(wèn)有路徑的節(jié)點(diǎn)，選擇路徑最小的節(jié)點(diǎn)，然后對(duì)這個(gè)節(jié)點(diǎn)，進(jìn)行看看，是否加了這個(gè)節(jié)點(diǎn)后，這個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的路徑是否變短了，如果有那么就更新路徑。然后一直重復(fù)，直到訪問(wèn)完所有的節(jié)點(diǎn)。
五．實(shí)驗(yàn)實(shí)習(xí)結(jié)果及分析
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-802298.html
實(shí)驗(yàn)結(jié)果成功。
六．實(shí)驗(yàn)遇到的問(wèn)題及解決辦法，實(shí)驗(yàn)心得體會(huì)及對(duì)此實(shí)驗(yàn)的意見(jiàn)或建議（有就寫(xiě)，無(wú)可不寫(xiě)）。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-802298.html
#include <stdio.h>
#include <stdlib.h>
#define MAX 99999
#define MAXVEX 100
#define true 1
#define false 0
int Path[MAXVEX];
int S[MAXVEX];
int D[MAXVEX];
typedef char Vexstype;
typedef int Arctype;
typedef struct Graph
{
Vexstype vex[MAXVEX];//頂點(diǎn)
Arctype arc[MAXVEX][MAXVEX];//鄰接矩陣
int vexnum, arcnum;//頂點(diǎn)和邊數(shù)
}Graph;
int locatenum(Graph* city, char citynum)
{
int i;
for (i = 0; i < city->vexnum; i++)
{
if (citynum == city->vex[i])
{
return i;
}
}
}
int Init(Graph* city,char *start,char *end)
{
int i;
int j;
int weight;
char city1, city2;
printf("請(qǐng)輸入城市個(gè)數(shù)和路徑條數(shù)\n");
scanf("%d %d", &city->vexnum,&city->arcnum);
fflush(stdin);
if (city->vexnum == 0 || city->arcnum == 0)
{
return 0;
}
printf("請(qǐng)輸入城市名\n");
fflush(stdin);
for (i = 0; i < city->vexnum; i++)
{
scanf(" %c", &city->vex[i]);
}
for (i = 0; i < city->vexnum; i++)
{
for (j = 0; j < city->vexnum; j++)
{
city->arc[i][j] = MAX;
}
}
fflush(stdin);
printf("請(qǐng)輸入路徑\n");
for (i = 0; i < city->arcnum; i++)
{
scanf(" %c %c %d", &city1, &city2, &weight);
fflush(stdin);
city->arc[locatenum(city, city1)][locatenum(city, city2)] = weight;
}
fflush(stdin);
printf("請(qǐng)輸入起點(diǎn)和終點(diǎn)\n");
scanf(" %c %c", &(*start), &(*end));
return 1;
}
void dijikstra(Graph* city, char start, char end)
{
int start_num = locatenum(city, start);
int i;
int min = MAX;
for (i = 0; i < city->vexnum; i++)
{
S[i] = false;
D[i] = city->arc[start_num][i];
if (D[i] < MAX)
{
Path[i] = start_num;
}
else
{
Path[i] = -1;
}
}
S[start_num] = true;
D[start_num] = 0;
int other;
int min_num=i;
for (i = 1; i < city->vexnum; i++)
{
min = MAX;
for (other = 0; other < city->vexnum; other++)
{
if (S[other] == false && D[other] < min)
{
min = D[other];
min_num = other;
}
}
S[min_num] = true;
for (other = 0; other < city->vexnum; other++)
{
if (S[other] == false && (D[min_num] + city->arc[min_num][other] < D[other]))
{
D[other] = D[min_num] + city->arc[min_num][other];
Path[other] = min_num;
}
}
}
}
void printPath(Graph* city, int end_num)
{
if (Path[end_num] != -1)
{
printPath(city, Path[end_num]);
}
printf("%c ", city->vex[end_num]);
}
void findend(Graph* city, char end)
{
int end_num = locatenum(city, end);
printf("最短長(zhǎng)度為%d\n", D[end_num]);
int i;
fflush(stdin);
printf("最短路徑為\n");
printPath(city, end_num);
printf("\n");
}
int main()
{
Graph city;
int vexnum, arcnum;
char start, end;
while (Init(&city,&start,&end))
{
dijikstra(&city, start, end);
findend(&city, end);
}
return 0;
}
到了這里，關(guān)于實(shí)驗(yàn)六 基于 Dijsktra 算法的最短路徑求解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
