2015/06/22

【C++】Floyd Warshall (all pairs shortest path)




使用時機：
1. 求任兩點間最短距離。
2, 求strongly connected component （兩兩之間互相走得到）
3. 因極易寫，在n<300時又不用back track時，可捨棄Dijkstra
4. 當需要back track，改Dijkstra做n次

初始化
?
1
2
3
4
5
6
7
8
#define INF 1<<18
 
int adj[MAX][MAX];
 
void init(){
    memset(adj, INF, sizeof(adj));
    for (int i=0; i< MAX; i++) adj[i][i] = 0;
}

Floyd Warshall simple sample code

?
1
2
3
4
5
6
7
void floyd_warshall(){
    for (int k=1; k<=n; k++)
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                if (adj[i][j] > adj[i][k]+adj[k][j])
                    adj[i][j] = adj[i][k] + adj[k][j];
}


求strongly connected
做完floyd warshall後，若( adj[u][v]<INF && adj[v][u]<INF)，則u和v在同個圈圈裡
範例：【UVa】247-Calling Circles (floyd_warshell)

於