<li id="qoecs"></li>

<center id="qoecs"></center>

»論壇 › 電子技術(shù)分類討論區(qū) › 程序設(shè)計(jì)/上位機(jī) › 弗洛伊德算法和迪杰斯特拉算法求最短路徑 VC++6.0源程序

返回列表

查看: 2541|回復(fù): 0

弗洛伊德算法和迪杰斯特拉算法求最短路徑 VC++6.0源程序

[復(fù)制鏈接]

電梯直達(dá)

樓主

ID:767505 發(fā)表于 2020-6-3 20:40 | 只看該作者回帖獎(jiǎng)勵(lì)

|倒序?yàn)g覽 |閱讀模式

實(shí)驗(yàn)一弗洛伊德算法
實(shí)驗(yàn)?zāi)康模焊ヂ逡恋滤惴ㄇ笞疃搪窂?br /> 實(shí)驗(yàn)內(nèi)容：

#include <stdio.h>
void main()
{
int e[9][9],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf(infinity的縮寫)存儲一個(gè)我們認(rèn)為的正無窮值
scanf("%d %d",&n,&m);//讀入n和m，n表示頂點(diǎn)個(gè)數(shù)，m表示邊的條數(shù)
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//讀入邊
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
}

復(fù)制代碼

/* 測試數(shù)據(jù) n=4 m=5
邊的數(shù)據(jù)
1 2 5
1 3 6
2 3 1
2 4 4
3 4 4
輸出結(jié)果
0       5       6          9
99999999 0       1          4
99999999 99999999 0          4
99999999 99999999 99999999 0

*/

實(shí)驗(yàn)一迪杰斯特拉算法
實(shí)驗(yàn)?zāi)康模旱辖芩固乩惴ㄇ笞疃搪窂?br /> 實(shí)驗(yàn)內(nèi)容：

#include<stdio.h>
#define SIZE 110
#define INF 1000000;
int map[SIZE][SIZE]; //鄰接矩陣存儲
int len[SIZE]; //d[i]表示源點(diǎn)到i這個(gè)點(diǎn)的距離
int visit[SIZE]; //節(jié)點(diǎn)是否被訪問
int n,m;
int dijkstra(int from, int to)//從源點(diǎn)到目標(biāo)點(diǎn)
{
int i;
for(i = 1 ; i <= n ; i ++)//初始化
{
visit[i] = 0; //一開始每個(gè)點(diǎn)都沒被訪問
len[i] = map[from][i]; //先假設(shè)源點(diǎn)到其他點(diǎn)的距離
}
int j;
for(i = 1 ; i < n ; ++i)//對除源點(diǎn)的每一個(gè)點(diǎn)進(jìn)行最短計(jì)算
{
int min = INF; //記錄最小len[i]
int pos; //記錄小len[i] 的點(diǎn)
for(j = 1 ; j <= n ; ++j)
{
if(!visit[j] && min > len[j])
{
pos = j;
min = len[j];
}
}
visit[pos] = 1;
for(j = 1 ; j <= n ; ++j)
{
if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
{ //如果j節(jié)點(diǎn)沒有被訪問過&&j節(jié)點(diǎn)到源節(jié)點(diǎn)的最短路徑>pos節(jié)點(diǎn)到源節(jié)點(diǎn)的最短路徑+pos節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)的路徑
len[j] = len[pos] + map[pos][j]; //更新j節(jié)點(diǎn)到源節(jié)點(diǎn)的最短路徑
}
}
}
return len[to];
}
int main ()
{
int i,j;
// scanf("%d%d",&n,&m); //輸入數(shù)據(jù)
n = 6; //測試數(shù)據(jù)
m = 9;
for(i = 1 ; i <= n ; ++i)
{ //設(shè)一開始每個(gè)點(diǎn)都不可達(dá)
for(j = 1 ; j <= n ; ++j)
{
map[i][j] = INF;
}
}
/* int a,b,c; //輸入數(shù)據(jù)
for(i = 1 ; i <= m ; ++i)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b] = map[b][a] = c;
} */
map[1][2] = 5; //測試數(shù)據(jù)
map[1][3] = 8;
map[1][6] = 3;
map[1][4] = 7;
map[2][3] = 4;
map[3][6] = 9;
map[4][6] = 6;
map[5][6] = 1;
map[4][5] = 5;
map[3][4] = 5;
int temp = INF;
for(i = 1 ; i <= n ; ++i)
{
for(j = 1 ; j <= n ; ++j)
{
if(map[i][j] == temp)
map[i][j] = map[j][i];
}
}
int ans = dijkstra(1,5);
printf("%d",ans);
return 0;
}