floyd最短路径

在对于多点之间求最短路径

1. 可以运行 |v| 次的Dijkstra算法求，尤其是稀疏图，效率更好

2. 可以采用floyd算法，运行时间为O( | v^3 | )，不是对于Dijkstra算法的 |v|

   次迭代，而且更紧凑，也可以针对Dijkstra算法不能对负边进行处理有了弥补，但是负值圈下面代码没有考虑。

#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 10
#define INFINITY 100

struct graphNode{
    int nV;
    int nE;
    int G[MAXNUM][MAXNUM];
    char data[MAXNUM];
};
typedef struct graphNode* gn;
struct ENode{
    int vb,ve;
    int weight;
};
typedef struct ENode* edge;
int D[MAXNUM][MAXNUM];
int Path[MAXNUM][MAXNUM];
gn createG(int nv)
{
    int v1,v2;
    gn g = (gn)malloc(sizeof(struct graphNode));
    g->nV = nv;
    g->nE = 0;
    for(v1 = 0; v1 < g->nV; v1++)
        for(v2 = 0; v2 < g->nV; v2++)
            g->G[v1][v2] = INFINITY;
    return g;
}
void insertEdge(gn g, edge e)
{
    //有向图
    g->G[e->vb][e->ve] = e->weight;
}
gn buildgraph()
{
    int nv;
    scanf("%d",&nv);
    gn g = createG(nv);
    scanf("%d",&(g->nE));
    if(g->nE != 0){
        edge e = (edge)malloc(sizeof(struct ENode));
        for(int i = 0; i < g->nE; i++){
            scanf("%d %d %d", &e->vb, &e->ve, &e->weight);
            insertEdge(g, e);
        }
        free(e);
    }
    for(int i = 0; i < g->nV; i++)
        scanf(" %c",&(g->data[i]));
    return g;
}
void floyd(gn g)
{
    //对于D数组的(i==j)的情况要让其值等于0,因为本身到本身的距离最短为0
    //对于Path数组在初始化的时候把有边的情况存成边的起点
    //不然对于两个点之间就本身的边最短,但是存成-1,就无法找到起点
    for(int i = 0; i < g->nV; i++){
        for(int j = 0; j < g->nV; j++){
            if(i == j) D[i][j] = 0;
            else D[i][j] = g->G[i][j];
            Path[i][j] = -1;
            if(g->G[i][j] != INFINITY) Path[i][j] = i; 
            else Path[i][j] = -1;
        }
    }
    for(int k = 0; k < g->nV; k++){
        for(int i = 0; i < g->nV; i++){
            for(int j = 0; j < g->nV; j++){
                if(D[i][j] > D[i][k]+D[k][j]){
                    D[i][j] = D[i][k]+D[k][j];
                    Path[i][j] = Path[k][j];
                }

            }
        }
    }
}
void printfloyd(gn g)
{
    printf("distance: \n");
    for(int i = 0; i < g->nV; i++){
        for(int j = 0; j < g->nV; j++){
            if(D[i][j] != INFINITY && D[i][j] != 0)
                printf("%d\t",D[i][j]);
            else
                printf("-\t");
        }
        printf("\n");
    }
    printf("\n");
    printf("path: \n");
    for(int i = 0; i < g->nV; i++){
        for(int j = 0; j < g->nV; j++){
            printf("%d\t",Path[i][j]);
        }
        printf("\n");
    }
}
int main(void)
{
    gn g = buildgraph();
    floyd(g);
    printfloyd(g);
    free(g);
    getchar();
    return 0;
}

           

参考

浙大数据结构，数据结构与算法分析