|
|
實驗一 弗洛伊德算法
實驗目的：弗洛伊德算法求最短路徑
實驗內容：
- #include <stdio.h>
- void main()
- {
- int e[9][9],k,i,j,n,m,t1,t2,t3;
- int inf=99999999; //用inf(infinity的縮寫)存儲一個我們認為的正無窮值
- scanf("%d %d",&n,&m);//讀入n和m，n表示頂點個數，m表示邊的條數
- //初始化
- 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");
- }
-
- }
/* 測試數據 n=4 m=5
邊的數據
1 2 5
1 3 6
2 3 1
2 4 4
3 4 4
輸出結果
0 5 6 9
99999999 0 1 4
99999999 99999999 0 4
99999999 99999999 99999999 0
*/
實驗一 迪杰斯特拉算法
實驗目的：迪杰斯特拉算法求最短路徑
實驗內容：
- #include<stdio.h>
- #define SIZE 110
- #define INF 1000000;
- int map[SIZE][SIZE]; //鄰接矩陣存儲
- int len[SIZE]; //d[i]表示源點到i這個點的距離
- int visit[SIZE]; //節點是否被訪問
- int n,m;
- int dijkstra(int from, int to)//從源點到目標點
- {
- int i;
- for(i = 1 ; i <= n ; i ++)//初始化
- {
- visit[i] = 0; //一開始每個點都沒被訪問
- len[i] = map[from][i]; //先假設源點到其他點的距離
- }
- int j;
- for(i = 1 ; i < n ; ++i)//對除源點的每一個點進行最短計算
- {
- int min = INF; //記錄最小len[i]
- int pos; //記錄小len[i] 的點
- 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節點沒有被訪問過&&j節點到源節點的最短路徑>pos節點到源節點的最短路徑+pos節點到j節點的路徑
- len[j] = len[pos] + map[pos][j]; //更新j節點到源節點的最短路徑
- }
- }
- }
- return len[to];
- }
- int main ()
- {
- int i,j;
- // scanf("%d%d",&n,&m); //輸入數據
- n = 6; //測試數據
- m = 9;
- for(i = 1 ; i <= n ; ++i)
- { //設一開始每個點都不可達
- for(j = 1 ; j <= n ; ++j)
- {
- map[i][j] = INF;
- }
- }
- /* int a,b,c; //輸入數據
- for(i = 1 ; i <= m ; ++i)
- {
- scanf("%d%d%d",&a,&b,&c);
- map[a][b] = map[b][a] = c;
- } */
- map[1][2] = 5; //測試數據
- 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;
- }
/* 邊的數據
1 2 5
1 3 8
1 6 3
1 4 7
2 3 4
3 6 9
5 6 1
4 5 5
3 4 5
*/
|
評分
-
查看全部評分
|
