当前位置：首页 > article >正文

c/c++蓝桥杯经典编程题100道（22）最短路径问题

article 2025/2/24 6:16:59

最短路径问题

->返回c/c++蓝桥杯经典编程题100道-目录

最短路径问题

一、题型解释

二、例题问题描述

三、C语言实现

解法1：Dijkstra算法（正权图，难度★★）

解法2：Bellman-Ford算法（含负权边，难度★★★）

四、C++实现

解法1：Dijkstra算法（优先队列优化，难度★★☆）

解法2：Floyd-Warshall算法（多源最短路径，难度★★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C++ STL的优先队列

2. 动态规划思想

3. 负权环检测

一、题型解释

最短路径问题是图论中的核心问题，目标是找到图中两点间权重和最小的路径。常见题型：

单源最短路径：求某一点到其他所有点的最短路径（如Dijkstra、Bellman-Ford算法）。
多源最短路径：求所有点对之间的最短路径（如Floyd-Warshall算法）。
特殊场景：
- 含负权边的最短路径（Bellman-Ford）。
- 含负权环的检测（Bellman-Ford扩展）。
- 边权为1的图（BFS优化）。

二、例题问题描述

例题1（单源正权图）：

输入：图的邻接矩阵，起点为A。
输出：A到各顶点的最短距离（如A→D的最短距离为5）。

例题2（含负权边）：

输入：带负权边的图，检测是否存在负权环。
输出：若存在环返回false，否则返回最短路径。

例题3（多源最短路径）：

输入：任意两点间的最短距离矩阵。
输出：更新后的最短距离矩阵。

三、C语言实现

解法1：Dijkstra算法（正权图，难度★★）

通俗解释：

贪心策略：每次选择当前距离起点最近的节点，逐步扩展最短路径集合。
适用条件：边权非负。

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

#define V 6  // 顶点数

int minDistance(int dist[], int visited[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (!visited[v] && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];      // 存储最短距离
    int visited[V];   // 记录节点是否已处理

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

    dist[src] = 0;  // 起点到自身距离为0

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited); // 选取未处理的最小距离节点
        visited[u] = 1;

        // 更新相邻节点的距离
        for (int v = 0; v < V; v++)
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX &&
                dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    // 输出结果
    printf("顶点\t距离\n");
    for (int i = 0; i < V; i++)
        printf("%d\t%d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0},
        {4, 0, 8, 0, 0, 0},
        {0, 8, 0, 7, 0, 4},
        {0, 0, 7, 0, 9, 14},
        {0, 0, 0, 9, 0, 10},
        {0, 0, 4, 14, 10, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

代码逻辑：

初始化：距离数组dist设为无穷大，起点距离为0。
循环处理：每次选择未访问的最小距离节点，更新其邻居的距离。
时间复杂度：O(V²)，适合稠密图。

解法2：Bellman-Ford算法（含负权边，难度★★★）

通俗解释：

松弛操作：通过多次迭代所有边，逐步逼近最短路径。
附加功能：可检测负权环。

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

#define E 8  // 边数
#define V 5  // 顶点数

struct Edge {
    int src, dest, weight;
};

void bellmanFord(struct Edge edges[], int src) {
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // 松弛所有边V-1次
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int w = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }

    // 检测负权环
    for (int j = 0; j < E; j++) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int w = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("图中存在负权环！\n");
            return;
        }
    }

    // 输出结果
    printf("顶点\t距离\n");
    for (int i = 0; i < V; i++)
        printf("%d\t%d\n", i, dist[i]);
}

int main() {
    struct Edge edges[E] = {
        {0, 1, -1}, {0, 2, 4}, {1, 2, 3},
        {1, 3, 2}, {1, 4, 2}, {3, 2, 5},
        {3, 1, 1}, {4, 3, -3}
    };
    bellmanFord(edges, 0);
    return 0;
}

代码逻辑：

初始化：所有距离设为无穷大，起点为0。
松弛操作：进行V-1轮边遍历更新距离。
负权环检测：若第V轮仍有更新，说明存在负权环。
时间复杂度：O(VE)，适合稀疏图。

四、C++实现

解法1：Dijkstra算法（优先队列优化，难度★★☆）

通俗解释：

使用优先队列快速获取最小距离节点，时间复杂度优化至O((V+E)logV)。

cpp

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

typedef pair<int, int> pii; // {距离, 节点}

void dijkstra(vector<vector<pii>> &graph, int src) {
    int V = graph.size();
    vector<int> dist(V, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue; // 跳过旧数据

        for (auto &edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "顶点\t距离" << endl;
    for (int i = 0; i < V; i++)
        cout << i << "\t" << dist[i] << endl;
}

int main() {
    int V = 5;
    vector<vector<pii>> graph(V);
    graph[0].push_back({1, 4});
    graph[0].push_back({2, 1});
    graph[1].push_back({3, 2});
    graph[2].push_back({1, 1});
    graph[2].push_back({3, 5});
    graph[3].push_back({4, 3});

    dijkstra(graph, 0);
    return 0;
}

代码逻辑：

优先队列：存储{距离, 节点}，自动按距离排序。
懒惰删除：当队列中的距离大于记录的距离时跳过。
STL使用：vector存邻接表，priority_queue实现最小堆。

解法2：Floyd-Warshall算法（多源最短路径，难度★★★）

通俗解释：

动态规划：通过中间节点逐步优化所有点对的最短路径。

cpp

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

#define INF INT_MAX

void floydWarshall(vector<vector<int>> &graph) {
    int V = graph.size();
    vector<vector<int>> dist = graph;

    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // 输出结果
    cout << "最短路径矩阵：" << endl;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++)
            cout << (dist[i][j] == INF ? "INF" : to_string(dist[i][j])) << "\t";
        cout << endl;
    }
}

int main() {
    vector<vector<int>> graph = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };
    floydWarshall(graph);
    return 0;
}

代码逻辑：

初始化距离矩阵：直接复制图的邻接矩阵。
三重循环：依次考虑每个中间节点k，更新所有i→j路径。
时间复杂度：O(V³)，适合小规模图。

五、总结对比表

算法	时间复杂度	空间复杂度	适用场景
Dijkstra	O((V+E)logV)	O(V)	正权图单源最短路径
Bellman-Ford	O(VE)	O(V)	含负权边的单源最短路径
Floyd-Warshall	O(V³)	O(V²)	多源最短路径