lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

Floyd_Warshall算法

Posted on 2009-04-11 03:14 lzmagic 阅读(2004) 评论(0)  编辑 收藏 引用 所属分类: Algorithm
/**
 * FLOYD_WARSHALL 所有顶点对的最短路径算法 (All-Pairs Shortest Path Algorithm)
 * 输入：图g
 * 输出：所有顶点对的最短路径长
 * 结构：图g用邻接矩阵表示
 * 算法：Floyd_Warshall算法(动态规划)
 * 复杂度：O(|V|^3) 
 */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;
vector<vector<int> > g;
vector<vector<int> > dist;

void Floyd_Warshall()
{
    // 初始化dist，顶点间(无中间顶点)最短路径长为边长，顶点到自身的最短路径长为0。 
    dist = g;
    for (int i = 0; i < n; ++i)  
        dist[i][i] = 0;
    // 从顶点i到定点j且中间顶点皆属于集合{0, 1, 2, , k}的最短路径长。 
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    n = 5;    
    g.assign(n, vector<int>(n, INT_MAX));
    g[0][1] = 3; g[0][2] = 8; g[0][4] = -4;
    g[1][3] = 1; g[1][4] = 7;
    g[2][1] = 4; 
    g[3][0] = 2; g[3][2] = -5;
    g[4][3] = 6;
     
    Floyd_Warshall();
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << dist[i][j] << ' ';
        cout << endl;        
    }
    
    system("pause");
    return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理