图之 最短路径 Floyd算法

最短路径之Floyd算法

描述

---

每一对顶点之间的最短路径

算法实现

---

初始时设置一个n阶方阵，令其对角线元素为0，若存在弧

逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值

所有顶点试探完毕，算法结束

初始化设置两个矩阵A和Path,A用来记录当前已经求得的任意两个顶点最短路径的长度，Path用来记录当前两顶点间最短路径上要经过的中间顶点

代码实现

---

#include<stdio.h>
#include<iostream>
#include<malloc.h>
using namespace std;
#define maxsize 100
#define INFINITY 65535

typedef struct
{
    int edges[maxsize][maxsize];
    int n, e;
}MGraph;

void CreateMGraph(MGraph &G)
{
    int i, j;
    int v1, v2, w;
    cin >> G.n >> G.e;
    for (i = 1; i <= G.n; i++)
    {
        for (j = 1; j <= G.n; j++)
        {
            if (i == j)
            {
                G.edges[i][j] = 0;
            }
            else
            {
                G.edges[i][j] = INFINITY;
            }
        }
    }
    for (i = 1; i <= G.e; i++)
    {
        cin >> v1 >> v2 >> w;
        G.edges[v1][v2] = w;    //有向图
    }
}

void print(int a[][maxsize], int n)
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

void Floyd(MGraph G, int A[][maxsize], int path[][maxsize])
{
    int i, j, k;
    for (i = 1; i <= G.n; i++)
    {
        for (j = 1; j <= G.n; j++)
        {
            A[i][j] = G.edges[i][j];
            path[i][j] = -1;
        }
    }
    for (k = 1; k <= G.n; k++)   //相当于经过k个点的中转寻找最短的那个
    {
        for (i = 1; i <= G.n; i++)
        {
            for (j = 1; j <= G.n; j++)
            {
                if (A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}


int main()
{
    //freopen("E:\input.txt", "r", stdin);
    MGraph G;
    CreateMGraph(G);
    int A[maxsize][maxsize];
    int path[maxsize][maxsize];
    Floyd(G, A, path);
    print(A, G.n);
    printf("\n");
    print(path, G.n);
    printf("\n");
    return 0;
}

Input

---

4 8
1 2 5
1 4 7
2 3 4
2 4 2
3 1 3
3 2 3
3 4 2
4 3 1

Output

---

0 5 8 7
6 0 3 2
3 3 0 2
4 4 1 0

-1 -1 4 -1 4 -1 4 -1
-1 -1 -1 -1 3 3 -1 -1

数据图例