8.3.1 蓝桥杯图论之Floyd&Dijkstra-Toy模板网

这篇具有很好参考价值的文章主要介绍了8.3.1 蓝桥杯图论之Floyd&Dijkstra。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

8.1.3 蓝桥杯图论之Floyd与Dijkstra算法

在蓝桥杯等算法竞赛中，图论问题占据了重要地位，其中路径查找是一个经常出现的主题。Floyd-Warshall算法和Dijkstra算法是解决图中最短路径问题的两种经典算法。本篇博客将介绍这两种算法的原理和实现，以及它们的应用场景。

Floyd-Warshall算法

Floyd-Warshall算法是一种计算图中所有最短路径的动态规划算法。它能够处理包括负权边的图，但不能处理有负权环的图。算法的核心思想是逐步检查所有顶点对，考虑是否通过一个中间顶点来缩短当前的最短路径。

算法原理

初始化距离矩阵，对于每一对顶点，如果它们之间有边直接相连，则距离为边的权重，否则距离为无穷大。
通过三重循环，逐步尝试将每一个顶点作为中间点，更新其他所有顶点对之间的最短距离。

C++实现

#include <iostream>
#include <vector>
using namespace std;

#define INF 99999
#define V 4

void printSolution(int dist[][V]);
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]) {
    cout << "The following matrix shows the shortest distances between every pair of vertices \n";
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                cout << "INF" << "     ";
            else
                cout << dist[i][j] << "     ";
        }
        cout << endl;
    }
}

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

Dijkstra算法

Dijkstra算法是一种用于在加权图中找到单源最短路径的贪心算法。它适用于含有非负权重边的图。算法的核心思想是持续更新起点到图中各顶点的最短路径长度。

算法原理

初始化距离数组，起点到自身的距离为0，到其他所有点的距离为无穷大。

使用一个集合来跟踪已经访问过的顶点。

#include <iostream>
#include <vector>
#include <climits>
#include <set>
using namespace std;

#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void printSolution(int dist[]) {
    cout << "Vertex \t Distance from Source\n";
    for (int i = 0; i < V; i++)
        cout << i << " \t\t" << dist[i] << endl;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        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, 0, 10, 0, 2, 0, 0},
                        {0, 0, 0, 14, 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;
}

对于每次迭代，从未访问的顶点中选出距离最小的一个，更新它的邻接顶点的距离。

C++实现

结语

Floyd-Warshall算法和Dijkstra算法是解决图中最短路径问题的两种重要算法。Floyd-Warshall适用于计算图中所有顶点对之间的最短路径，而Dijkstra算法适用于计算单源最短路径。它们各有优势和局限性，在不同的应用场景下选择合适的算法是解决问题的关键。希望本篇博客能帮助你理解这两种算法的原理和实现，为蓝桥杯等算法竞赛做好准备。

8.3.1 蓝桥杯图论之Floyd&Dijkstra,蓝桥杯,蓝桥杯,图论,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-825796.html