一、實(shí)驗(yàn)?zāi)康?/p>
講清楚進(jìn)行本實(shí)驗(yàn)后要學(xué)到的知識(shí)、掌握的數(shù)據(jù)結(jié)構(gòu)及其定義和表示方法，講清楚所采用的算法。
掌握?qǐng)D結(jié)構(gòu)的（鄰接矩陣）輸入方法
掌握?qǐng)D結(jié)構(gòu)的說(shuō)明、創(chuàng)建以及圖的存儲(chǔ)表示（鄰接矩陣）
掌握最短路徑算法原理
掌握最短路徑算法的編程實(shí)現(xiàn)方法
二、實(shí)驗(yàn)要求
講清楚進(jìn)行本實(shí)驗(yàn)之前需要的先驗(yàn)知識(shí)及條件
熟悉C++語(yǔ)言編程
熟悉圖的鄰接矩陣存儲(chǔ)表示
熟悉最短路徑算法原理
熟悉使用C++語(yǔ)言，實(shí)現(xiàn)最短路徑算法
先驗(yàn)知識(shí)：
迪杰特斯拉算法思想：
設(shè)G=（V,E）是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一章為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑，就將加入到集合S中。直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了）。第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)V到S中各頂點(diǎn)的最短路徑長(zhǎng)度大于從源點(diǎn)V到V中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從V到此頂點(diǎn)的最短路徑長(zhǎng)度，V中的頂點(diǎn)的距離是從V到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。
三、實(shí)驗(yàn)內(nèi)容
講清楚本實(shí)驗(yàn)的內(nèi)容，以及為實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容所采用算法的原理
四、實(shí)驗(yàn)步驟
? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
五、完整代碼（可直接run）? （編譯環(huán)境vscode）
#include<stdio.h>
#define MAXVERTEXNUM 100 //定義數(shù)組長(zhǎng)度
#define INFINITY 100//定義無(wú)窮
struct Graph{
? ? int VertexNum;//圖中頂點(diǎn)個(gè)數(shù)
? ? char Vertex[MAXVERTEXNUM];//將圖的頂點(diǎn)字母存入數(shù)組
? ? int AdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM];//設(shè)置領(lǐng)接矩陣用兩個(gè)數(shù)組
};
Graph MGraph;
char Path[MAXVERTEXNUM][MAXVERTEXNUM];//設(shè)置圖的鄰接矩陣
int Dest[MAXVERTEXNUM];//全局設(shè)置權(quán)值
void CreateGraph(Graph *G);//生成圖調(diào)用函數(shù)
void ShowGraph(Graph *G);//展示圖調(diào)用函數(shù)
void ShortestPath(Graph *G, char StartVexChar);//測(cè)試路徑
void ShowPath(Graph *G); //展示路徑
int main(){ ?
? ? char StartVex;//
? ?
? ? CreateGraph(&MGraph);
? ? ShowGraph(&MGraph);
? ? printf("請(qǐng)輸入開(kāi)始的頂點(diǎn)");
? ? scanf("%c", &StartVex);
? ? ShortestPath(&MGraph, StartVex);
? ? ShowPath(&MGraph);
? ? return 0;
}文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-457063.html
//
void CreateGraph(Graph *G){
? ? int i, j;
? ?
? ? printf("請(qǐng)輸入頂點(diǎn)個(gè)數(shù)\n");
? ? scanf("%d", &G->VertexNum);
? ? printf("請(qǐng)輸入頂點(diǎn)\n");
? ? getchar();
? ? for(i = 1; i <= G->VertexNum; i++){
? ? ? ? scanf("%c", &G->Vertex[i]);
? ? ? ? getchar();
? ? }文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-457063.html
? ? printf("請(qǐng)輸入鄰接矩陣\n");
? ? for(i = 1; i <= G->VertexNum; i++){
? ? ? ? for(j = 1; j <= G->VertexNum; j++){
? ? ? ? ? ? scanf("%d", &G->AdjMatrix[i][j]);
? ? ? ? ? ? getchar();
? ? ? ? ? ? if(G->AdjMatrix[i][j] == -1)
? ? ? ? ? ? ? ?G->AdjMatrix[i][j] = INFINITY;
? ? ? ? } ?
? ? }
}
void ShowGraph(Graph *G){
? ? int i, j;
? ? for(i = 1; i <= G->VertexNum; i++){
? ? ? ? printf("%c ", G->Vertex[i]);
? ? }
? ? putchar('\n');
? ? for(i = 1; i <= G->VertexNum; i++){
? ? ? ? for(j = 1; j <= G->VertexNum; j++){
? ? ? ? ? ? printf("%d ", G->AdjMatrix[i][j]);
? ? ? ? }
? ? ? ? putchar('\n'); ?
? ? }
}
void ShortestPath(Graph *G, char StartVexChar){
? ? int i, j, m, StartVex, CurrentVex, MinDest, Final[MAXVERTEXNUM];
? ? for (i = 1; i <= G->VertexNum; i++){
? ? ? ? if(G->Vertex[i] == StartVexChar){
? ? ? ? ? ? StartVex = i;
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? for (i = 1; i <= G->VertexNum; i++){
? ? ? ? Path[i][0] = 0;
? ? ? ? Dest[i] = INFINITY;
? ? ? ? if(G->AdjMatrix[StartVex][i] < INFINITY){
? ? ? ? ? ? Dest[i] = G->AdjMatrix[StartVex][i];
? ? ? ? ? ? Path[i][1] = G->Vertex[StartVex];
? ? ? ? ? ? Path[i][2] = G->Vertex[i];
? ? ? ? ? ? Path[i][0] = 2;
? ? ? ? }
? ? ? ? Final[i] = 'F';
? ? }
? ? Dest[StartVex] = 0;
? ? Final[StartVex] = 'T';
? ? for (i = 1; i <= G->VertexNum; i++){
? ? ? ? MinDest = INFINITY;
? ? ? ? for (j = 1; j <= G->VertexNum; j++){
? ? ? ? ? ? if(Final[j] == 'F'){
? ? ? ? ? ? ? ? if(Dest[j] < MinDest){
? ? ? ? ? ? ? ? ? ? CurrentVex = j;
? ? ? ? ? ? ? ? ? ? MinDest = Dest[j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? Final[CurrentVex] = 'T';
? ? ? ? for (j = 1; j <= G->VertexNum; j++){
? ? ? ? ? ? if((Final[j] == 'F') && (MinDest + G->AdjMatrix[CurrentVex][j]) < Dest[j]){
? ? ? ? ? ? ? ? Dest[j] = MinDest + G->AdjMatrix[CurrentVex][j];
? ? ? ? ? ? ? ? for(m = 0; m <= Path[CurrentVex][0]; m++)
? ? ? ? ? ? ? ? ? ? Path[j][m] = Path[CurrentVex][m];
? ? ? ? ? ? ? ? Path[j][0]++;
? ? ? ? ? ? ? ? Path[j][Path[j][0]] = G->Vertex[j];
? ? ? ? ? ? }
? ? ? ? } ? ?
? ? } ?
}
void ShowPath(Graph *G){
? ? int i, j;
? ? for(i= 1; i <= G->VertexNum; i++){
? ? ? ? printf("%c(%d):", G->Vertex[i], Dest[i]);
? ? ? ? if(Path[i][0] > 0){
? ? ? ? ? ? for(j = 1; j <= Path[i][0]; j++){
? ? ? ? ? ? ? ? printf(" %c", Path[i][j]);
? ? ? ? ? ? } ? ? ?
? ? ? ? }
? ? ? ? printf("%c\n", Path[i][j]);
? ? }
}
到了這里，關(guān)于圖的最短路徑 （數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
