最短路徑課程設(shè)計(jì)課件

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)10/9/20221一、需求分析對(duì)于任意圖，選擇存儲(chǔ)結(jié)構(gòu)存儲(chǔ)并實(shí)現(xiàn)FLOYED算法求解最短路徑。它將問(wèn)題分解為兩個(gè)方面，一是對(duì)于任意圖的存儲(chǔ)問(wèn)題，二是實(shí)現(xiàn)floyed算法求解最短路徑。首先對(duì)于圖的創(chuàng)建選擇合適的存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，對(duì)于合適的存儲(chǔ)結(jié)構(gòu)可以簡(jiǎn)化程序。在floyed算法中路徑的長(zhǎng)度既是圖中兩頂點(diǎn)間邊的權(quán)值，要求輸出任意兩頂點(diǎn)間的最短路徑，而且經(jīng)過(guò)的頂點(diǎn)也要輸出。10/9/20222二 概要設(shè)計(jì)本程序包含的函數(shù)：1.主函數(shù)main（）2 鄰接矩陣創(chuàng)建函數(shù)create（）3 FLOYED算法函數(shù)floyed（）4 輸出函數(shù)dispath（）10/9/202235 前遞歸輸出

2、函數(shù)ppath（）各函數(shù)關(guān)系如下：10/9/20224三、詳細(xì)設(shè)計(jì)#include#include#define ma 100#define Null 0#define INF 9999typedef structint data;int num;vertex;typedef structint n; /頂點(diǎn)個(gè)數(shù)int e; /邊個(gè)數(shù)vertex vexsma; /存儲(chǔ)頂點(diǎn)int edgesmama; /存儲(chǔ)邊的權(quán)值mgraph; /鄰接矩陣存儲(chǔ)圖void main()dispath;mgraph *mg;mg=create();floyd(mg);10/9/20225void ppath(i

3、nt pathma,int i,int j) /向前遞歸查找路徑上的頂點(diǎn)int k;k=pathij;if(k=-1) return;ppath(path,i,k);printf(%d-,k);ppath(path,k,j);返回main（）10/9/20227void floyd(mgraph *g) /floyd算法處理矩陣int Amama,pathmama;int i,j,k;for(i=1;in;i+)for(j=1;jn;j+)Aij=g-edgesij;pathij=-1;for(k=1;kn;k+)for(i=1;in;i+)for(j=1;jn;j+) if(Aik!=0&Akj!=0&Aij(Aik+Akj)Aij=Aik+Akj;pathij=k; printf(n輸出最