图——图的应用02最短路径（Dijkstra算法与Floyd算法详解）

2024-07-16 16:11:21

前面介绍了图的应用——01最小生成树章节，大家可以通过下面的链接学习：

图——图的应用01最小生成树（Prim算法与Kruskal算法详解）

今天就讲一下图的另一个应用——最短路径。

两种常见的最短路径问题：

一、单源最短路径—用Dijkstra（迪杰斯特拉）算法

二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法

Dijkstra（迪杰斯特拉）算法

Dijkstra算法思想

1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。

2.选择：从这些路径中找出一条长度最短的路径（v0,u）。

3.更新：然后对其余各条路径进行适当调整，即：

从v0到其余各点的最短路径--按路径长度递增次序求解

1、把V分成两组：

(1) S：已求出最短路径的顶点的集合。

(2) T=V -S：尚未确定最短路径的顶点集合。

2、将T中顶点按最短路径递增的次序加入到S中，

保证：

(1)从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。

(2)每个顶点对应一个距离值：

S中顶点：从v0到此顶点的最短路径长度。

T中顶点：从v到此顶点的只包括S中顶点作中间顶点的最短路径长度。

下面是一个实例——

c语言中Dijkstra算法的完整代码：

#include <stdio.h>
#include <limits.h>

#define V 9

// 函数minDistance用于找到距离源节点最近的节点
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;
    // 遍历所有节点，找到距离源节点最近的节点
    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// 函数printSolution用于打印最短路径
void printSolution(int dist[]) {
    printf("Vertex \t\t Distance from Source");
    // 遍历所有节点，打印最短路径
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d", i, dist[i]);
}

// 函数dijkstra用于计算最短路径
void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];

    // 初始化距离数组和最短路径集合
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    dist[src] = 0;

    // 遍历所有节点，计算最短路径
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        // 更新距离数组
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    dijkstra(graph, 0);

    return 0;
}

结果如下：

Vertex    Distance from Source
0    0
1    4
2    12
3    19
4    21
5    11
6    9
7    8
8    14

Floyd（弗洛伊德）算法

求所有顶点间的最短路径有两种方法：

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。

方法二：弗洛伊德(Floyd)算法。

Floyd算法思想：

1、逐个顶点试探；

2、从????????v_i到????????v_j的所有可能存在的路径中

3、选出一条长度最短的路径

c语言中Floyd算法的完整代码：

与之前同样使用了“limits”库， "INF"表示两个顶点之间没有路径。使用INT_MAX来表示无穷大，当两个顶点之间没有直接路径时，它们的距离就是无穷大。

#include <stdio.h>
#include <limits.h>

#define V 4

// 打印最短路径矩阵
void printSolution(int dist[][V]);

// Floyd-Warshall算法
void floydWarshall(int graph[][V]) {
    int dist[V][V], i, j, k;

    // 初始化距离矩阵
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // 三重循环，计算最短路径
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 打印最短路径矩阵
    printSolution(dist);
}

// 打印最短路径矩阵
void printSolution(int dist[][V]) {
    printf("以下是最短路径矩阵：");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INT_MAX)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf(" \n");
    }
}

int main() {
    int graph[V][V] = {{0, 5, INT_MAX, 10},
                       {INT_MAX, 0, 3, INT_MAX},
                       {INT_MAX, INT_MAX, 0, 1},
                       {INT_MAX, INT_MAX, INT_MAX, 0}};

    // 调用Floyd-Warshall算法
    floydWarshall(graph);
    return 0;
}

输出结果：

以下是最短路径矩阵：
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

到此图的应用——最短路径就结束了，不知道大家对于Dijksra和Floyd两种算法有没有掌握呢？

如果文章对你有用的话请点个赞支持一下吧！

码农公寓