dijkstra算法之中的优化版算法

Question

dijkstra算法之中的优化版算法

#include<iostream>
#include<queue> 
#include<cstring>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+10;
int n,m;
int h[N],e[N],ne[N],idex,w[N],dis[N],visit[N];
void add(int x,int y,int z){
    e[idex]=y;
    w[idex]=z;
    ne[idex]=h[x];
    h[x]=idex++;
}
int dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    queue<PII>que;
    que.push({0,1});
    dis[1]=0;//首先是距离，第二个是点
    while(!que.empty()){
        auto t=que.front() ;
        que.pop() ;
        int ver=t.second,distance=t.first;
        if(visit[ver]) continue;
        visit[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>distance+w[i]){
                dis[j]=distance+w[i];
                que.push({dis[j],j});
            }
        }
    } 
    if(dis[n]==0x3f3f3f3f)  return -1;
    else return dis[n];
}
int main(){
    
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--){
        int x,y,z;
        cin>>x>>y>>z; 
        add(x,y,z);
    }
    cout<<dijkstra()<<endl;
    return 0;
} 

为什么以上代码在解决最短路径的问题中运行错误呢，

Answer 1

引自免费微信小程序：皆我百晓生

这个Dijkstra算法实现中存在一个潜在的错误，它可能导致算法无法找到正确的最短路径。问题出在对已经访问过的节点（即visit[ver]为真）的处理上。当节点被标记为已访问后，它们可能因为新加入边而变得更短，但原代码没有考虑到这种情况。

为了解决这个问题，我们需要稍微修改一下代码，在更新节点的距离时，无论该节点是否已被访问，都应检查并更新其距离。以下是修复后的代码：

#include<iostream>
#include<queue> 
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
int n, m;
int h[N], e[N], ne[N], idex, w[N], dis[N], visit[N];

void add(int x, int y, int z) {
    e[idex] = y;
    w[idex] = z;
    ne[idex] = h[x];
    h[x] = idex++;
}

int dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    queue<PII> que;
    que.push({0, 1});

    while (!que.empty()) {
        auto t = que.front();
        que.pop();
        int ver = t.second, distance = t.first;

        // 将这里的判断条件移除，以便总是检查所有边
        // if (visit[ver]) continue;

        visit[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dis[j] > distance + w[i]) {
                dis[j] = distance + w[i];
                que.push({dis[j], j});
            }
        }
    }

    if (dis[n] == 0x3f3f3f3f) return -1;
    else return dis[n];
}

int main() {

    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    cout << dijkstra() << endl;
    return 0;
}

在这个修复版本中，我删除了if (visit[ver]) continue;这一行，使得即使节点已经被访问，只要通过新的边可以得到更短的距离，也会进行更新。这样，Dijkstra算法就能正确地找出从源节点到目标节点的最短路径。