为何这段Dijkstra算法代码在有向图场景下无法正常工作？

云上老周

2026-9-3

Dijkstra算法在有向图上运行结果异常问题

这段Dijkstra算法代码无法在有向图上正确得到预期结果。
以下面的测试用例为例：

测试用例对应有向图规则：共4个节点、7条单向边，其中仅2->4为2到4的单向边，不存在4到2的直接边，节点4到节点2的正确最短路径为4->3->1->2，总长度为3。

测试用例运行代码后输出的节点4对应距离为1，和预期结果3不符，容易误以为算法把单向边当成了双向边处理，完整代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
const int INF = 1e9+10;
vector<pair<int,int>> g[N];
vector<int> vis(N,0);
vector<int> dist(N, INF);


void bfs(int source){

    set<pair<int,int>> st;

    st.insert({0,source});
    dist[source] = 0;

    while(st.size()>0){
        auto curr = *st.begin();
        int wt_v = curr.first;
        int v = curr.second;
        st.erase(st.begin());

        if(vis[v]) continue;
        vis[v] = 1;
        
        for(auto child:g[v]){

            int child_v = child.first;
            int wt = child.second;

            if(dist[v] + wt < dist[child_v]){
                dist[child_v] = dist[v] + wt;
                st.insert({dist[child_v],child_v});
            }
        }
    }
}


int main(){
    int n; cin>>n;
    int e; cin>>e;
    int t; cin>>t;
    int m; cin>>m;

    for (int i = 0; i < m; ++i){
        int v1,v2,wt; cin>>v1>>v2>>wt;
        g[v1].push_back({v2,wt});
    }

    bfs(e);

    for (int i = 1; i <= n; ++i){
        cout<<dist[i]<<endl;
    }
}

问题原因

代码的Dijkstra核心逻辑、有向边存储逻辑本身没有错误，没有把单向边错误处理为双向边，结果不符合预期的核心原因是搞反了单源最短路径的计算方向：

当前代码在原始有向图上以e为源点运行Dijkstra，最终dist[i]存储的是从源点e出发走到节点i的最短路径长度。测试用例中e=2，输出的dist[4] = 1对应的是2->4这条单向边的长度，这个结果本身是完全正确的。
你预期得到的“节点4到节点2的最短路径长度为3”，是从节点i出发走到目标点的最短路径长度，和当前代码计算的路径方向完全相反，相当于你需要的是多对一的最短路径，而当前代码实现的是一对多的最短路径。
另外代码中读入的变量t没有被任何逻辑使用，也是逻辑偏差的来源之一。

修正方案

如果需要计算所有节点到指定终点的最短路径，只需要调整建图逻辑，将所有边反向存储即可，反向建图后以终点为源点运行Dijkstra，得到的dist[i]就是原图中节点i到终点的最短路径长度：

for (int i = 0; i < m; ++i){
    int v1,v2,wt; cin>>v1>>v2>>wt;
    // 原逻辑存储v1->v2，计算从v1出发的单源路径
    // 反向存储v2->v1，即可在反向图上计算源点到各点的距离，等价于原图各点到源点的距离
    g[v2].push_back({v1,wt});
}

如果你的目标终点是读入的t，记得将Dijkstra的调用参数从bfs(e)改为bfs(t)。修正后运行测试用例，节点4对应的距离输出为3，符合预期。

内容的提问来源于stack exchange，提问作者Harsh Sharma