Tata: Created page with "*เป็น Algorithm หา Shortest Path ให้ทุกสองจุดใดๆ (หมายความว่า สามารถบอก Shortest Path จา..."

2019-03-07T17:13:09Z

Created page with "*เป็น Algorithm หา Shortest Path ให้ทุกสองจุดใดๆ (หมายความว่า สามารถบอก Shortest Path จา..."

New page

*เป็น Algorithm หา Shortest Path ให้ทุกสองจุดใดๆ (หมายความว่า สามารถบอก Shortest Path จากจุด u ไป v ได้เลย)
*โดยใช้ Time: O(V^3)
*เก็บเป็น Adjacency Matrix ใช้ Space: O(V^2)
*เริ่มต้นต้องกำหนดให้ระยะทาง dist[u][v] ทุกๆช่องเป็น INF ก่อน (INF คือเสมือนกับว่าไม่มีทางเดินจาก u->v)
/*
" FLOYD-WARSHALL"
AUTHOR: ROOS
DATE: 23/3/2012
*/
#include<stdio.h>
#define N_VERTEX 1000
#define INF 1000000000
int dist[N_VERTEX+5][N_VERTEX+5], nVertex, nEdge;
int main()
{
int u, v, weight;
scanf("%d%d",&nVertex,&nEdge);
//Initial
for(int i=1; i<=nVertex; i++)
for(int j=1; j<=nVertex; j++)
dist[i][j] = INF;
//Input
for(int i=1; i<=nEdge; i++)
{
scanf("%d%d%d",&u,&v,&weight);
dist[u][v] = weight; //not any two edge have same (u,v)
dist[v][u] = weight; //not any two edge have same (u,v)
}
//Floyd-Warshall O(V^3)
for(int k=1; k<=nVertex; k++)
for(int i=1; i<=nVertex; i++)
for(int j=1; j<=nVertex; j++)
if(dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];

//Show Result
printf("===== Shortest Path =====\n");
for(int i=1; i<=nVertex; i++)
for(int j=1; j<=nVertex; j++)
printf("from %d\tto %d\t= %d\n",i,j,dist[i][j]);
scanf(" ");
return 0;
}
/*
5 5
1 3 5
1 2 3
1 5 9
2 5 2
3 4 1
*/

Floyd-Warshall - Revision history

Tata: Created page with "*เป็น Algorithm หา Shortest Path ให้ทุกสองจุดใดๆ (หมายความว่า สามารถบอก Shortest Path จา..."