最短路径(Floyd算法和Dijkstra算法和Bellman-Ford算法)

完全最短路径(Floyd算法)：[复杂度：O(n^3)]

// 矩阵mat初始值INT_MAX  

// 结果 mat[i][j] 为点i到j的最短路径  

// mat[i][j] == INT_MAX时候为不可到达  

   

void Floyd(int n)  

{   

    int i, j, k;  

    for (k = 1; k <= n; k++)  

        for (i = 1; i <= n; i++)  

            for (j = 1; j <= n; j++)  

                if (mat[i][k] != INT_MAX &&  

                    mat[k][j] != INT_MAX &&  

                    mat[i][k]+mat[k][j] < mat[i][j])  

                        mat[i][j] = mat[i][k] + mat[k][j];  

} 

单源最短路径Dijkstra算法：

// mat初始值为INT_MAX，即不可到达  

// s表示起始点，p重点，n节点个数，返回s到p的最短路径  

// 当返回结果为INT_MAX时，表示不可达  

// 结果dis为第s点到其他点的最短路径  

   

int dis[MAXN];  

bool flag[MAXN];  

int mat[MAXN][MAXN];  

   

void Dijkstra(int s, int p, int n)  

{  

    int i, j;  

    for (i = 1; i <= n; i++)  

        dis[i] = mat[s][i], flag[i] = false;  

    flag[s] = true, dis[s] = 0;  

   

    for (i = 1; i <= n; i++)  

    {  

        int k = s, t = INT_MAX;  

        for (j = 1; j <= n; j++)  

            if (!flag[j] && dis[j] < t)  

                k = j, t = dis[j];  

        flag[k] = true;  

        for (j = 1; j <= n; j++)  

            if (!flag[j] && mat[k][j] != INT_MAX  

                && dis[k] + mat[k][j] < dis[j])  

                    dis[j] = dis[k] + mat[k][j];  

    }  

} 

Bellman-Ford算法：

适用范围：

1. 单源最短路径(从源点s到其它所有顶点v);
2. 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3. 边权可正可负(如有负权回路输出错误提示);
4. 差分约束系统;

算法描述：

1. 对每条边进行|V|-1次Relax操作;
2. 如果存在(u,v)∈E使得dis[u]+w<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。

For i:=1 to |V|-1 do //v为顶点数

For 每条边(u,v)∈E do //对每条边进行遍历

Relax(u,v,w);

For 每条边(u,v)∈E do

If dis[u]+w<dis[v] Then Exit(False)