如何用Dijkstra算法求关联矩阵表示的带权有向图最短路径？

网上能找到的Dijkstra算法大多基于邻接矩阵实现，目前需要针对给定的带权有向图关联矩阵，实现从键盘输入的起始顶点到其余所有顶点的最短路径求解，输出每条路径的权重及经过的顶点。

给定的关联矩阵说明 #

该带权有向图包含8个顶点（编号0-7），关联矩阵每行代表一条有向边：

• 首行是顶点编号：0 1 2 3 4 5 6 7
• 每行开头的{起点;终点}表示边的方向，后续列中仅终点对应的位置为边的权重，其余为0
• 完整边信息及对应权重如下：
  • {0;1} → 权重1
  • {0;2} → 权重2
  • {1;2} → 权重1
  • {1;3} → 权重5
  • {1;4} → 权重2
  • {2;3} → 权重2
  • {2;4} → 权重1
  • {2;5} → 权重4
  • {3;4} → 权重3
  • {3;5} → 权重6
  • {3;6} → 权重8
  • {4;5} → 权重3
  • {4;6} → 权重7
  • {5;6} → 权重5
  • {5;7} → 权重2
  • {6;7} → 权重6

你已用vector存储关联矩阵的权重部分：

vector<vector<int>> incidenceMatrix = {
  {0,1,0,0,0,0,0,0},
  {0,0,2,0,0,0,0,0},
  {0,0,1,0,0,0,0,0},
  {0,0,0,5,0,0,0,0},
  {0,0,0,0,2,0,0,0},
  {0,0,0,2,0,0,0,0},
  {0,0,0,0,1,0,0,0},
  {0,0,0,0,0,4,0,0},
  {0,0,0,0,3,0,0,0},
  {0,0,0,0,0,6,0,0},
  {0,0,0,0,0,0,8,0},
  {0,0,0,0,0,3,0,0},
  {0,0,0,0,0,0,7,0},
  {0,0,0,0,0,0,5,0},
  {0,0,0,0,0,0,0,2},
  {0,0,0,0,0,0,0,6},
};

实现思路 #

由于Dijkstra算法核心是处理顶点的邻接关系，我们先将关联矩阵转换为邻接表（存储每个顶点能到达的所有顶点及对应边权），再用标准Dijkstra框架计算最短路径：

1. 定义每条边的起点和终点对应关系，匹配关联矩阵的行
2. 遍历关联矩阵，构建邻接表
3. 使用优先队列（小顶堆）优化Dijkstra的顶点选择过程
4. 记录每个顶点的最短距离及前驱顶点，最终回溯前驱得到完整路径

完整代码实现 #

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
    // 关联矩阵：每行对应一条边的权重分布
    vector<vector<int>> incidenceMatrix = {
        {0,1,0,0,0,0,0,0},
        {0,0,2,0,0,0,0,0},
        {0,0,1,0,0,0,0,0},
        {0,0,0,5,0,0,0,0},
        {0,0,0,0,2,0,0,0},
        {0,0,0,2,0,0,0,0},
        {0,0,0,0,1,0,0,0},
        {0,0,0,0,0,4,0,0},
        {0,0,0,0,3,0,0,0},
        {0,0,0,0,0,6,0,0},
        {0,0,0,0,0,0,8,0},
        {0,0,0,0,0,3,0,0},
        {0,0,0,0,0,0,7,0},
        {0,0,0,0,0,0,5,0},
        {0,0,0,0,0,0,0,2},
        {0,0,0,0,0,0,0,6},
    };

    // 每条边的起点和终点，与incidenceMatrix的行一一对应
    vector<pair<int, int>> edges = {
        {0,1}, {0,2}, {1,2}, {1,3}, {1,4},
        {2,3}, {2,4}, {2,5}, {3,4}, {3,5},
        {3,6}, {4,5}, {4,6}, {5,6}, {5,7}, {6,7}
    };

    int vertexCount = 8; // 顶点总数0-7
    // 构建邻接表：adj[u]存储所有从u出发的边，pair<终点, 权重>
    vector<vector<pair<int, int>>> adj(vertexCount);
    for (int i = 0; i < incidenceMatrix.size(); ++i) {
        int u = edges[i].first;
        int v = edges[i].second;
        int weight = incidenceMatrix[i][v]; // 终点列对应的权重
        adj[u].emplace_back(v, weight);
    }

    // 输入起始顶点
    int start;
    cout << "请输入起始顶点编号（0-7）：";
    cin >> start;
    if (start < 0 || start >= vertexCount) {
        cout << "顶点编号非法！" << endl;
        return 1;
    }

    // 初始化距离数组和前驱数组
    vector<int> dist(vertexCount, INT_MAX);
    vector<int> prev(vertexCount, -1);
    dist[start] = 0;

    // 优先队列：小顶堆，存储<当前距离, 顶点>，每次取距离最小的顶点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, start);

    // Dijkstra算法核心
    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();

        // 如果当前记录的距离已经更小，跳过该顶点
        if (currentDist > dist[u]) continue;

        // 遍历u的所有邻接顶点
        for (auto [v, weight] : adj[u]) {
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
                pq.emplace(dist[v], v);
            }
        }
    }

    // 输出结果
    cout << "从顶点" << start << "到各顶点的最短路径：" << endl;
    for (int v = 0; v < vertexCount; ++v) {
        if (v == start) continue;
        cout << "顶点" << start << " → 顶点" << v << "：";
        if (dist[v] == INT_MAX) {
            cout << "无可达路径" << endl;
            continue;
        }
        cout << "总权重=" << dist[v] << "，路径：";
        // 回溯前驱节点得到路径
        vector<int> path;
        for (int cur = v; cur != -1; cur = prev[cur]) {
            path.push_back(cur);
        }
        reverse(path.begin(), path.end());
        // 输出路径
        for (size_t i = 0; i < path.size(); ++i) {
            if (i > 0) cout << " → ";
            cout << path[i];
        }
        cout << endl;
    }

    return 0;
}

代码说明 #

• 邻接表构建：通过edges数组匹配每条边的起点和终点，从关联矩阵中提取权重，转换为邻接表格式，方便Dijkstra处理
• 优先队列优化：使用小顶堆确保每次取出当前距离最小的顶点，提升算法效率
• 路径回溯：通过prev数组记录每个顶点的前驱节点，反向遍历得到完整路径后反转输出

内容的提问来源于stack exchange，提问作者Denis Bredun