最短路径(C语言, floyd算法)

#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/* * 代码实现<<大话数据结构>>p267 图7-7-13,和dijkstra算法同一张图 * v0至v8分别用ABCDEFGHI代替 * 时间复杂度O(n)^3, 虽然比dijkstra O(n)^2慢，但是可以求得任意顶点间的最短路径及开销 */#define MAX 9#define INFINITY 65535typedef int NextPoint[MAX][MAX]; // 存放v到w的最短路径时要先经过的顶点,非parent关系typedef int PathMatrix[MAX][MAX]; // 存放各顶点间的最短路径开销, D数组// 图结构体typedef struct {    char vexs[MAX]; // 顶点的数组，顶点类型为了简单使用char    int arc[MAX][MAX]; // 边表二维数组，值为权    int numVex;}GRAPH, *PGRAPH;void create(PGRAPH);void gprint(GRAPH);void addEdge(PGRAPH, int, int, int);void floyd(GRAPH, PathMatrix *, NextPoint *);void floyd(GRAPH graph, PathMatrix *D, NextPoint *P){    int v, w, k;    // 初始化D, P数组    for (v=0; v<graph.numVex; v++) {        for (w=0; w<graph.numVex; w++) {            (*D)[v][w] = graph.arc[v][w];            (*P)[v][w] = w;        }    }    /* 开始循环查找最短路径，更新D P数组       k为中转顶点，用于比对是否v经过k到w的开销比D数组中当前更小       如果更小，则说明k更有可能存在于v到w最短路径上，更新D，及P    */    for (k=0; k<graph.numVex; k++) {        // v行        for (v=0; v<graph.numVex; v++) {            // v行所有w列             for (w=0; w<graph.numVex; w++) {                // 判断k是否有可能在v和w的最短路径上                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {                    // 更新两点间的距离和                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];                     //因为k存在于v到w的路径上，所以v想要到w需要先经过 v到k要经过的顶点                    (*P)[v][w] = (*P)[v][k];                 }            }        }    }}void addEdge(PGRAPH g, int i, int j, int v){    g->arc[i][j] = g->arc[j][i] = v;}void create(PGRAPH g){    int i, j;    g->numVex = 9;    // 创建顶点    g->vexs[0] = 'A';    g->vexs[1] = 'B';    g->vexs[2] = 'C';    g->vexs[3] = 'D';    g->vexs[4] = 'E';    g->vexs[5] = 'F';    g->vexs[6] = 'G';    g->vexs[7] = 'H';    g->vexs[8] = 'I';    // 初始化边表矩阵    for (i=0; i<g->numVex; i++) {        for (j=0; j<g->numVex; j++) {            g->arc[i][j] = INFINITY;            if (j == i)                g->arc[i][j] = 0; //行列相等时表示自身，标识为0        }    }    // 添加边及权值    // A v0, B v1, C v2, D v3, E v4, F v5, G v6, H v7, I, v8    addEdge(g, 0, 1, 1);    addEdge(g, 0, 2, 5);    addEdge(g, 1, 2, 3);    addEdge(g, 1, 4, 5);    addEdge(g, 1, 3, 7);    addEdge(g, 2, 4, 1);    addEdge(g, 2, 5, 7);    addEdge(g, 3, 4, 2);    addEdge(g, 3, 6, 3);    addEdge(g, 4, 5, 3);    addEdge(g, 4, 7, 9);    addEdge(g, 4, 6, 6);    addEdge(g, 5, 7, 5);    addEdge(g, 6, 7, 2);    addEdge(g, 6, 8, 7);    addEdge(g, 7, 8, 4);}void gprint(GRAPH graph){    int i, j;    for (i=0; i<graph.numVex; i++) {        for (j=0; j<graph.numVex; j++){            printf("%6d ", graph.arc[i][j]);        }        putchar('\n');    }}int main(void){    int i, j, k;    GRAPH graph;    NextPoint next_point;    PathMatrix distance;    create(&graph);    gprint(graph);    floyd(graph, &distance, &next_point);    printf("D数组(任意顶点间的最短路径开销或者叫距离)\n");    for (i=0; i<MAX; i++) {        for (j=0; j<MAX; j++) {            printf("%6d ", distance[i][j]);        }        putchar('\n');    }    printf("任意顶点间的最短路径:\n");    for (i=0; i<MAX; i++) {        for (j=i+1; j<MAX; j++) {            printf("%d -> %d distance: %3d, path:", i, j, distance[i][j]);            printf("%d->", i); // 先打印源点            k = next_point[i][j];            while (k != j) {                printf("%d->", k);                k = next_point[k][j]; // 相当于递归查找            }            printf("%d\n", k);        }    }    return 0;}

output

# gcc shortestPath_floyd.c && ./a.out     0      1      5  65535  65535  65535  65535  65535  65535      1      0      3      7      5  65535  65535  65535  65535      5      3      0  65535      1      7  65535  65535  65535  65535      7  65535      0      2  65535      3  65535  65535  65535      5      1      2      0      3      6      9  65535  65535  65535      7  65535      3      0  65535      5  65535  65535  65535  65535      3      6  65535      0      2      7  65535  65535  65535  65535      9      5      2      0      4  65535  65535  65535  65535  65535  65535      7      4      0 D数组(任意顶点间的最短路径开销或者叫距离)     0      1      4      7      5      8     10     12     16      1      0      3      6      4      7      9     11     15      4      3      0      3      1      4      6      8     12      7      6      3      0      2      5      3      5      9      5      4      1      2      0      3      5      7     11      8      7      4      5      3      0      7      5      9     10      9      6      3      5      7      0      2      6     12     11      8      5      7      5      2      0      4     16     15     12      9     11      9      6      4      0 任意顶点间的最短路径:0 -> 1 distance:   1, path:0->10 -> 2 distance:   4, path:0->1->20 -> 3 distance:   7, path:0->1->2->4->30 -> 4 distance:   5, path:0->1->2->40 -> 5 distance:   8, path:0->1->2->4->50 -> 6 distance:  10, path:0->1->2->4->3->60 -> 7 distance:  12, path:0->1->2->4->3->6->70 -> 8 distance:  16, path:0->1->2->4->3->6->7->81 -> 2 distance:   3, path:1->21 -> 3 distance:   6, path:1->2->4->31 -> 4 distance:   4, path:1->2->41 -> 5 distance:   7, path:1->2->4->51 -> 6 distance:   9, path:1->2->4->3->61 -> 7 distance:  11, path:1->2->4->3->6->71 -> 8 distance:  15, path:1->2->4->3->6->7->82 -> 3 distance:   3, path:2->4->32 -> 4 distance:   1, path:2->42 -> 5 distance:   4, path:2->4->52 -> 6 distance:   6, path:2->4->3->62 -> 7 distance:   8, path:2->4->3->6->72 -> 8 distance:  12, path:2->4->3->6->7->83 -> 4 distance:   2, path:3->43 -> 5 distance:   5, path:3->4->53 -> 6 distance:   3, path:3->63 -> 7 distance:   5, path:3->6->73 -> 8 distance:   9, path:3->6->7->84 -> 5 distance:   3, path:4->54 -> 6 distance:   5, path:4->3->64 -> 7 distance:   7, path:4->3->6->74 -> 8 distance:  11, path:4->3->6->7->85 -> 6 distance:   7, path:5->7->65 -> 7 distance:   5, path:5->75 -> 8 distance:   9, path:5->7->86 -> 7 distance:   2, path:6->76 -> 8 distance:   6, path:6->7->87 -> 8 distance:   4, path:7->8

©著作权归作者所有：来自51CTO博客作者sndapk的原创作品，如需转载，请注明出处，否则将追究法律责任

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

每一份赞赏源于懂得

更多相关文章

随机推荐