Dijkstra最短路径的复杂度

Question

我似乎不明白 Wikipedia's paragraph 为什么 Dijkstra 最短路径问题是 O((|E|+|V|)*log(|V|))

假设我使用二叉堆，提取所有顶点需要V*logV，E*logV项从何而来？

谁能赐教吗？

Answer 1

当你从堆中提取一个顶点时，你需要检查所有从该节点出来的边，并对每个邻居做一些处理（递减键）。

这意味着我们最终会在整个算法中检查所有边，并且可能需要每个边的 O(logV)，因此除了 O(VlogV) 的成本之外，总共需要 O(ElogV) 来移除最小值每个顶点的堆条目。

Answer 2

在 Dijstra 算法中，基本上您将所有可用的顶点作为选项添加，然后选择其中的最小值。基本上按部就班

节点：只有源：边：从源出来的直接边。

添加每条边需要 log(Edge_taken_in) 时间取其中最小的那一个。

添加从您刚刚发现的节点出来的所有边，添加到达该节点的成本，并将它们全部添加到我们的堆或任何 O(log(n)) 工作数据结构中并重复。

好的，现在这些步骤将继续进行，直到发现每个顶点。

对于每个顶点，您将添加从它出去的所有边（最大值可能是 O(V)（如果节点连接到所有其他节点））。
删除最小值并重新制作堆/（和 DS u 使用）。

好的，我们有两件事要处理。

第一个 O(V) 插入 V 次给出

O((V^2)log(V))

(你可能会说 V^2(log(E))

但这将与

相同

log (E) = log(V^2) = O(log(V))).

现在第二步将以最小成本提取边得到的每个节点进行V次。

因此

T = O( (V^2)log(V) + (V)O(log(V)))

现在为 E=O(V^2) Sp我们可能会说。

T=O((E+V) log(V)).

这是代码

#include<iostream>
#include<vector>
#include<utility>
#include<limits.h>
#include<queue>
using namespace std;
class compare{
public:
  bool operator()(pair<int ,int> p,pair<int ,int> q)
  {
    if(p.first<q.first)
      return false;
    else
      return true;
  }
};
int main()
{
  int count,min,mini,n,m,i,x,y,d,s;
  cin>>n>>m;
  int a[n];
  bool b[n];
  priority_queue<pair<int ,int>,vector<pair<int , int> >,compare>pq; 
  pair<int ,int>p;
  vector<pair<int ,int > >V[n];
  for(i=0;i<m;++i)
    {
      cin>>x>>y>>d;
      //  x--;y--;
      p.first=y;
      p.second=d;
      V[x].push_back(p);
      p.first=x;
      V[y].push_back(p);
    }
  while(1)
    {
      cout<<"Enter the Source\t";
      cin>>s;
      for(i=0;i<n;++i)
    {
      a[i]=INT_MAX;
      b[i]=false;
    }
      count=1;
      a[s]=0;
      p=make_pair(a[s],s);
      pq.push(p);
      // s--;
      min=0;
      while(!pq.empty() && pq.top().first!=INT_MAX)
    {
      p=pq.top();
      pq.pop();
      cout<<p.first<<" "<<p.second<<endl;
      if(b[p.second]==true)
        {
          continue;
        }
      else
        {
          //in v second is distance and first is index
          mini=p.second;
          for(i=0;i<V[mini].size();++i)
        {
          cout<<i<<" "<<V[mini][i].first<<" "<<a[V[mini][i].first]<<" "<<a[mini]+V[mini][i].second<<endl;
          if(b[V[mini][i].first]==false&&a[V[mini][i].first]>a[mini]+V[mini][i].second)
            {
              a[V[mini][i].first]=a[mini]+V[mini][i].second;
              p=make_pair(a[V[mini][i].first],V[mini][i].first);

              cout<<" *"<<p.first<<" "<<p.second<<endl;
              pq.push(p);
            }
        }
          b[mini]=true;
        }
      cout<<endl<<endl;
    }

      for(i=0;i<n;++i)
    cout<<a[i]<<" ";
      cout<<endl;


    }
  return 0;
}

Dijkstra最短路径的复杂度

Complexity of Dijkstra shortest path

language-agnostic

algorithm

time-complexity