最短路径问题
目录

最短路径问题

一、题型解释

二、例题问题描述

三、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)，适合稀疏图。