在 stl 中使用向量和对的最有效实现 Dijkstra 最短路径C++

Question

>如果std::vector<vector<pair<int,int> > > v(n)表示图形的邻接列表，pair<int,int>是{vertex,weight}对，我尝试通过以下方式实现算法：

while (true)
{
    long long yo = LLONG_MAX;
    int ind = -1;
    for (int i = 0; i < n; ++i)
    {
        if (ans[i] < yo && !v[i].empty())
        {
            ind = i;
            yo = ans[i];
        }
    }
    if (ind == -1)
        break;
    for (int i = 0; i < v[ind].size(); ++i)
    {
        if (ans[v[ind][i].first] > ans[ind] + v[ind][i].second)
            ans[v[ind][i].first] = ans[ind] + v[ind][i].second;
        v[ind].erase(v[ind].begin() + i);
    }
}

其中ans[i]存储初始化为{LLONG_MAX,...0,...LLONG_MAX}的最短路径，0作为源。由于这是我第一次尝试实现它，有没有更好的方法在 stl 中使用向量/列表实现(就时间/空间复杂性而言(？

Answer 1

当前的方法有逻辑错误(在迭代时修改向量(。同样在复杂性方面，它似乎也非常糟糕，因为冗余的while循环每次都获取新的最小距离节点和不必要的擦除操作，由于整个邻接列表的移动，矢量很重。

我建议使用优先级队列<最小堆>，它更干净，并且具有Elog(N(的复杂性，其中E是no.的边和N个no.的节点在图中。我只是复制粘贴带有注释的旧代码之一。

#define P first
#define Q second 
typedef long long LL ;
typedef pair < LL , int > li ;
typedef pair < int , LL > il ;
dist[N] = {INT_MAX} ;  // array containing the distance to each node from source node 
vector < il > adj [100010] ; // adjacency list with (node, distance) pair 
void dijkstra( int s ){   // s is the source node
  priority_queue < li , vector < li > , greater < li > > pq; // priortiy queue with a pair <long, int> as the data , using vector as underlying data structure and std:greater comparator 
  dist [s] = 0;
  pq.push( li( dist[s], s) );
  while( !pq.empty() ){
      li u = pq.top() ; pq.pop() ; // u.P =  current minimum distance of node , u.Q = current node on top of the heap 
      if( dist[u.Q] == u.P )
      for( int i = 0 ; i  < adj[u.Q].size() ; i++){
           il v = adj[u.Q][i] ;
           if( dist[v.P] > u.P + v.Q ){
               dist[v.P] = u.P + v.Q ;
               pq.push( li(dis[v.P] ,v.P ));
           }
      } 
  }

如果您有任何问题，请随时在评论中提问。

Answer 2

优化Dijkstra的一些方法：

1. 使用堆。确保存储顶点，而不是堆中的边。
2. 尝试双向方法。假设，您必须找到从 S 到 T 的最短路径。您可以同时运行 2 个 Dijkstra：一个像往常一样来自 S，另一个来自反转边缘的 T。您可以使用某种启发式方法在这 2 个 Dijkstras 之间切换。例如，使用电流半径最小的 Dijkstra。

从理论上讲，Dijkstra 可以用斐波那契堆优化为 O(E + VlogV(。但在实践中，它的工作速度较慢。