-
大小: 1.17MB文件類型: .zip金幣: 2下載: 0 次發(fā)布日期: 2023-10-04
- 語言: 其他
- 標(biāo)簽: 數(shù)據(jù)結(jié)構(gòu)??
資源簡介
數(shù)據(jù)結(jié)構(gòu)_導(dǎo)航最短路徑查詢課外實踐,迪杰斯特拉算法 弗洛伊德算法

代碼片段和文件信息
#include
#include
using?namespace?std;
//*******************圖的鄰接矩陣表示*************
typedef?struct
{
char*vexs; //頂點向量;
int?**arcs; //鄰接矩陣;
int?vexnumarcnum; //圖的當(dāng)前頂點數(shù)和弧數(shù);
}MGraph;
//***********************************************
//***********查找u頂點在頂點向量中的位置*********
int?locate(MGraph?Gchar?u)
{
int?i;
int?k;
for(i=0;i {
if(u==G.vexs[i])
{
k=i;
break;
}
}
return?k;
}
//創(chuàng)建有向圖的鄰接矩陣存儲結(jié)構(gòu)
//此時.adj存儲弧的長度;
void?createMGraph(MGraph&mg)
{
int?ij;
ifstream?fin(“Floyd.txt“ios::in);//文件流類對象
if(!fin)//判斷文件流類對象是否創(chuàng)建成功
{
cout<<“文件無法打開!“< exit(0);
}
fin>>mg.vexnum>>mg.arcnum;//從文件輸入頂點數(shù)和邊數(shù)
mg.vexs=new?char[mg.vexnum];//開辟空間存儲各頂點
for(?i=0;i {
fin>>mg.vexs[i];//從文件輸入頂點
}
//*************開辟空間存儲鄰接矩陣*************
mg.arcs=new?int*[mg.vexnum];
for(i=0;i {
mg.arcs[i]=new?int[mg.vexnum];
}
//*****************end************************
for(i=0;i {
for(j=0;j {
fin>>mg.arcs[i][j];
cout< }
cout< }
}
//************求v0到其余各頂點的最短距離及路徑*****************
void?ShortestPath_DIJ(MGraph&Gint?v0int?*&Pint*&D)
{
int?ikjmin;
bool?*final=new?bool[G.vexnum];//標(biāo)志數(shù)組
P=new?int?[G.vexnum];//全局變量存儲路徑
D=new?int?[G.vexnum];//全局變量存儲最短距離
//初始化;
for(i=0;i {
final[i]=false;
D[i]=G.arcs[v0][i];
P[i]=v0;
}
final[v0]=true;//表示始點已求出最短路徑;
for(i=1;i {
//找一個頂點從v0到該頂點距離最短
min=1000;//min初始化為最大值
for(j=0;j {
if(!final[j]&&min>D[j])
{
min=D[j];
k=j;//記錄當(dāng)前距離最短的頂點
}
}
final[k]=true;//表示已求出v0到k的最短距離
//當(dāng)前最短路徑更新
for(j=0;j {
if(!final[j]&&(min+G.arcs[k][j]) {
D[j]=G.arcs[k][j]+min;
P[j]=k;
}
}
}
}
//輸出最短路徑(遞歸算法);//b到v0的路徑
void?explainPathRecursionDIJ(MGraph&Gint?*pathint?v0int?b)
{
int?k;
if(v0==b)
{
k=v0;
cout< }
else
{
explainPathRecursionDIJ(Gpathpath[v0]b);
k=v0;
cout< }
}
//輸出最短路徑及長度;//b到其余各頂點的路徑
void?printPathDIJ(MGraph&Gint?*pathint*dint?b)
{
int?n=G.vexnum;
int?i;
cout<<“始點“<<‘\t‘<<“終點“<<‘\t‘<<“最短路徑“<<“\t“<<“路徑長度“< for(i=0;i {
if(i!=b)
{
cout< explainPathRecursionDIJ(Gpathib);
cout<<“\t\t“< cout< }
}
cout< }
//Floyd算法//求有向網(wǎng)G中各對頂點v和w之間的最短路徑
void?ShortestPath_FLOYD(MGraph&Gint?**&pint?**&d)
{
int?ijk;
//開辟空間存儲最短路徑與最短距離(p和d都是二維的)
p=new?int?*[G.vexnum];
d=new?int?*[G.vexnum];
for(i=0;i {
p[i]=new?int?[G.vexnum];
d[i]=new?int?[G.vexnum];
}
//初始化
for(i=0;i {
for(j=0;j {
p[i][j]=i;//記錄初始路徑
d[i][j]=G.arcs[i][j];//記錄初始路徑長度
}
}
//求最短距離和最短路徑
for(k=0;k {
for(i=0
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2014-06-07?23:53??導(dǎo)航最短路徑查詢\
?????目錄???????????0??2014-06-07?23:53??導(dǎo)航最短路徑查詢\Debug\
?????文件???????74752??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\vc60.idb
?????文件??????118784??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\vc60.pdb
?????文件??????573538??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).exe
?????文件??????820400??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).ilk
?????文件??????355920??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).obj
?????文件?????2098908??2013-12-26?17:30??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).pch
?????文件?????1139712??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).pdb
?????文件?????????119??2013-12-14?19:35??導(dǎo)航最短路徑查詢\Floyd.txt
?????文件??????????44??2013-12-04?21:14??導(dǎo)航最短路徑查詢\Floyd2.txt
?????文件????????5238??2013-12-26?17:35??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).cpp
?????文件????????3475??2013-12-27?00:45??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).dsp
?????文件?????????532??2013-12-27?00:46??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).dsw
?????文件???????41984??2013-12-27?00:46??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).ncb
?????文件???????48640??2013-12-27?00:46??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).opt
?????文件????????1192??2013-12-27?00:45??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).plg
?????文件??????153600??2014-06-07?23:53??數(shù)據(jù)結(jié)構(gòu)_導(dǎo)航最短路徑查詢課外實踐報告.doc
- 上一篇:步進電機代碼
- 下一篇:惠普D2055d中文說明書
評論
共有 條評論