2

几天前，我学习了 Dijkstra 算法，并想学习制作一个新的无向图，该图具有与原始图的最短路径边。

所以我所做的是对 Dijkstra 最短路径算法进行了简单的修改。

#define ll long long
vector <pair<int,long long>> adj[N]; //original graph
vector <int> adjj[N]; //new graph with shortest path edges

void dijkstra(int s)
{
    d[s]=0;  // array that stores shortest path
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push(make_pair(0,s));
    while(!pq.empty())
    {
        int v=pq.top().S;ll dist=pq.top().F;
        pq.pop();

        if(dist==((long long)(1e18)))
            return;
        if(dist>d[v])
            continue;
        if(p[v]!=0) // considering nodes' number start from 1          
            // new graph made only with shortest paths  
            adjj[parent[v]].push_back(v),adjj[v].push_back(parent[v]); 
        for(auto edge : adj[v])
        {
            int to = edge.first;
            ll len = edge.second;
            if((len+d[v])<d[to])
            {
                parent[to]=v;
                d[to]=len+d[v];
                pq.push(make_pair(d[to],to));
            }
        }
    }
}

所以我在我的一些自定义测试用例上尝试了这段代码，但我不能完全确定这是正确的......如果你能告诉我这是对还是错，那就太好了？

4

1 回答 1

0

它是正确的。本质上，您在这里所做的是构建一个搜索树，以反映您的算法找到的路径。然而，这棵树通常是有向的，因为它是有根树。

有几点值得一提：

  • 您声明了一个#define您从未使用过的 ( ll)
  • 而不是在代码中硬编码无穷大，你应该有一个#define INF
  • 无需测试无穷大是否来自优先级队列。只有找到进入队列的路径后，才能将顶点推送到队列中
于 2019-07-18T00:00:36.937 回答