1. 最短路径问题概述

最短路径问题是图论中的经典问题，旨在寻找图中两个顶点之间路径权值之和最小的路径。这类问题在现实生活中有着广泛的应用，如GPS导航、网络路由、物流配送等。

1.1 问题分类

最短路径问题主要分为以下几类：

1. 单源最短路径：从一个顶点出发到其他所有顶点的最短路径
2. 单目标最短路径：从所有顶点到某一个顶点的最短路径
3. 单对顶点最短路径：两个特定顶点之间的最短路径
4. 所有顶点对最短路径：图中所有顶点之间的最短路径

1.2 常见算法

常用的最短路径算法包括：

• Dijkstra算法：适用于非负权图
• Bellman-Ford算法：可处理负权边
• Floyd-Warshall算法：计算所有顶点对最短路径
• A*算法：启发式搜索算法

2. 图的表示方法

在C++中实现最短路径算法前，我们需要先了解图的表示方法。

2.1 邻接矩阵

邻接矩阵是使用二维数组表示图的方法，适合稠密图。

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

class GraphMatrix {
private:
    int V; // 顶点数
    vector<vector<int>> matrix;
    
public:
    GraphMatrix(int vertices) : V(vertices) {
        matrix.resize(V, vector<int>(V, 0));
    }
    
    void addEdge(int u, int v, int weight) {
        matrix[u][v] = weight;
        matrix[v][u] = weight; // 无向图
    }
    
    void printGraph() {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                cout << matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    GraphMatrix g(5);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 4);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 7);
    g.addEdge(2, 4, 3);
    g.addEdge(3, 4, 1);
    
    g.printGraph();
    return 0;
}

 

邻接矩阵实现简单，但空间复杂度为O(V²)，不适合稀疏图。

2.2 邻接表

邻接表使用链表或动态数组存储每个顶点的邻接顶点，适合稀疏图。

 <iostream>
#include <vector>
#include <list>
#include <utility> // for pair
using namespace std;

class GraphList {
private:
    int V;
    vector<list<pair<int, int>>> adj; // 邻接表: pair<顶点, 权重>
    
public:
    GraphList(int vertices) : V(vertices), adj(V) {}
    
    void addEdge(int u, int v, int weight) {
        adj[u].push_back(make_pair(v, weight));
        adj[v].push_back(make_pair(u, weight)); // 无向图
    }
    
    void printGraph() {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << i << " 的邻接顶点: ";
            for (auto it = adj[i].begin(); it != adj[i].end(); ++it) {
                cout << "(" << it->first << ", " << it->second << ") ";
            }
            cout << endl;
        }
    }
};

int main() {
    GraphList g(5);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 4);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 7);
    g.addEdge(2, 4, 3);
    g.addEdge(3, 4, 1);
    
    g.printGraph();
    return 0;
}

邻接表空间复杂度为O(V+E)，更适合稀疏图。

3. Dijkstra算法实现

Dijkstra算法是解决单源最短路径问题的经典算法，适用于非负权图。

3.1 算法原理

1. 初始化：设置源点到自身的距离为0，其他顶点距离为无穷大
2. 选择当前距离最小的未访问顶点
3. 更新该顶点邻接顶点的距离
4. 重复步骤2-3，直到所有顶点都被访问

3.2 C++实现

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

typedef pair<int, int> iPair; // <距离, 顶点>

void dijkstra(const vector<vector<iPair>>& graph, int src) {
    int V = graph.size();
    vector<int> dist(V, INT_MAX);
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    
    dist[src] = 0;
    pq.push(make_pair(0, src));
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
            
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(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<iPair>> graph(V);
    
    // 构建图
    graph[0].push_back(make_pair(1, 2));
    graph[0].push_back(make_pair(2, 4));
    graph[1].push_back(make_pair(0, 2));
    graph[1].push_back(make_pair(2, 1));
    graph[1].push_back(make_pair(3, 7));
    graph[2].push_back(make_pair(0, 4));
    graph[2].push_back(make_pair(1, 1));
    graph[2].push_back(make_pair(4, 3));
    graph[3].push_back(make_pair(1, 7));
    graph[3].push_back(make_pair(4, 1));
    graph[4].push_back(make_pair(2, 3));
    graph[4].push_back(make_pair(3, 1));
    
    dijkstra(graph, 0);
    return 0;
}

Dijkstra算法时间复杂度为O((V+E)logV)，使用优先队列优化。

4. Bellman-Ford算法实现

Bellman-Ford算法可以处理负权边，并能检测负权环。

4.1 算法原理

1. 初始化所有顶点距离
2. 对每条边进行V-1次松弛操作
3. 检查是否存在负权环

4.2 C++实现

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

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

void bellmanFord(vector<Edge>& edges, int V, int E, int src) {
    vector<int> dist(V, 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 weight = edges[j].weight;
            
            if (dist[u] != INT_MAX && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    // 检查负权环
    for (int i = 0; i < E; ++i) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;
        
        if (dist[u] != INT_MAX && dist[v] > dist[u] + weight) {
            cout << "图中存在负权环!" << endl;
            return;
        }
    }
    
    cout << "顶点\t距离源点的最短距离" << endl;
    for (int i = 0; i < V; ++i) {
        cout << i << "\t" << dist[i] << endl;
    }
}

int main() {
    int V = 5;
    int E = 8;
    vector<Edge> edges = {
        {0, 1, 2}, {0, 2, 4}, {1, 2, 1},
        {1, 3, 7}, {2, 4, 3}, {3, 4, 1},
        {1, 0, 2}, {2, 0, 4}
    };
    
    bellmanFord(edges, V, E, 0);
    return 0;
}

Bellman-Ford算法时间复杂度为O(VE)，适合处理负权边。

5. Floyd-Warshall算法实现

Floyd-Warshall算法用于计算所有顶点对之间的最短路径。

5.1 算法原理

1. 初始化距离矩阵
2. 通过中间顶点k更新所有顶点对(i,j)的距离
3. 重复步骤2直到所有顶点都作为中间顶点被考虑

5.2 C++实现

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

#define INF INT_MAX

void printSolution(const vector<vector<int>>& dist, int V) {
    cout << "所有顶点对的最短距离矩阵:" << endl;
    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;
    }
}

void floydWarshall(vector<vector<int>>& graph, int V) {
    vector<vector<int>> dist(V, vector<int>(V));
    
    // 初始化距离矩阵
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            dist[i][j] = graph[i][j];
    
    // 更新距离矩阵
    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] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    printSolution(dist, V);
}

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

Floyd-Warshall算法时间复杂度为O(V³)，空间复杂度为O(V²)。

6. A*算法实现

A*算法是一种启发式搜索算法，常用于路径规划。

6.1 算法原理

1. 使用估价函数f(n) = g(n) + h(n)
   • g(n): 从起点到当前节点的实际代价
   • h(n): 从当前节点到终点的估计代价(启发式函数)
2. 维护开放列表和关闭列表
3. 每次选择f(n)最小的节点扩展

6.2 C++实现

 <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_set>
using namespace std;

struct Node {
    int x, y;
    double g, h;
    Node* parent;
    
    Node(int x, int y) : x(x), y(y), g(0), h(0), parent(nullptr) {}
    
    double f() const { return g + h; }
};

struct CompareNode {
    bool operator()(const Node* a, const Node* b) {
        return a->f() > b->f();
    }
};

double heuristic(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

vector<Node*> aStar(const vector<vector<int>>& grid, Node* start, Node* end) {
    int rows = grid.size();
    int cols = grid[0].size();
    
    priority_queue<Node*, vector<Node*>, CompareNode> openList;
    unordered_set<Node*> closedList;
    
    start->h = heuristic(start->x, start->y, end->x, end->y);
    openList.push(start);
    
    while (!openList.empty()) {
        Node* current = openList.top();
        openList.pop();
        
        if (current->x == end->x && current->y == end->y) {
            // 找到路径
            vector<Node*> path;
            while (current != nullptr) {
                path.push_back(current);
                current = current->parent;
            }
            return path;
        }
        
        closedList.insert(current);
        
        // 检查四个方向的邻居
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        for (int i = 0; i < 4; ++i) {
            int nx = current->x + dx[i];
            int ny = current->y + dy[i];
            
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == 1)
                continue;
            
            Node* neighbor = new Node(nx, ny);
            neighbor->parent = current;
            neighbor->g = current->g + 1;
            neighbor->h = heuristic(nx, ny, end->x, end->y);
            
            bool inClosed = false;
            for (auto node : closedList) {
                if (node->x == nx && node->y == ny) {
                    inClosed = true;
                    break;
                }
            }
            if (inClosed) continue;
            
            openList.push(neighbor);
        }
    }
    
    return {}; // 未找到路径
}

int main() {
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };
    
    Node* start = new Node(0, 0);
    Node* end = new Node(4, 4);
    
    vector<Node*> path = aStar(grid, start, end);
    
    if (!path.empty()) {
        cout << "找到路径:" << endl;
        for (int i = path.size() - 1; i >= 0; --i) {
            cout << "(" << path[i]->x << ", " << path[i]->y << ")";
            if (i != 0) cout << " -> ";
        }
        cout << endl;
    } else {
        cout << "未找到路径" << endl;
    }
    
    return 0;
}

A*算法性能取决于启发式函数的选择，好的启发式函数能显著提高搜索效率。

7. 性能比较与应用场景

7.1 算法比较

算法	时间复杂度	空间复杂度	适用场景
Dijkstra	O((V+E)logV)	O(V)	非负权图，单源最短路径
Bellman-Ford	O(VE)	O(V)	含负权边，单源最短路径
Floyd-Warshall	O(V³)	O(V²)	所有顶点对最短路径
A*	取决于启发式函数	O(V)	路径规划，启发式搜索

7.2 应用场景

1. ‌Dijkstra算法‌：GPS导航、网络路由协议(OSPF)
2. ‌Bellman-Ford算法‌：距离向量路由协议(RIP)、金融套利检测
3. ‌Floyd-Warshall算法‌：交通规划、社交网络分析
4. ‌A*算法‌：游戏AI路径规划、机器人导航

8. 优化技巧与扩展

8.1 优化技巧

1. ‌Dijkstra算法优化‌：

   • 使用斐波那契堆可将时间复杂度降至O(E + VlogV)
   • 双向搜索可减少搜索空间

2. ‌A*算法优化‌：

   • 使用更精确的启发式函数
   • 实现跳点搜索(JPS)优化

8.2 扩展应用

1. ‌K最短路径‌：寻找前K条最短路径
2. ‌动态最短路径‌：处理图中边权动态变化的情况
3. ‌多目标最短路径‌：考虑多个优化目标的最短路径