Блог пользователя BanazadehAria

Автор BanazadehAria, история, 5 лет назад, По-английски

Hi, What is the best way to get the shortest path from vertex a to b in a weighted undirected graph?

I have done this but can we do better than O(|V|)?

map<int,list<pair<int,int> > > adjList;

void addEdge(int u,int v,int weight){
    adjList[u].pb(mp(v,weight));
    adjList[v].pb(mp(u,weight));
}

void FindShortestPath(int u,int v){
    int dp[n];
    dp[u]=0;
    map<int,bool> visited;
    queue<int> q;q.push(u);visited[u]=true;
    while(!q.empty()){
        int now = q.front();q.pop();
        for(auto neight : adjList[now]){
            dp[neight.first] = min(dp[neight.first],dp[now]+neight.second);
            if(!visited[neight.first]){
                q.push(neight.first);visited[neight.first]=true;
            }
        }
    }cout << dp[v];
}
  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by BanazadehAria (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As far as I know, the best way to get the shortest path in a graph with positive weight is Dijkstra, and the complexity is $$$O(n\log n)$$$

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh no you don't. Let V be the vertex set and E be the edge set. Then complexity of dijkstra's shortest path algo is $$$O((|V|+|E|)log(|V|)) = O(|V^2|log(|V|))$$$

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

      Can u please elaborate, how O((v+e)log(v)) = O(v*v*log(v))?LanceTheDragonTrainer, I think it should be v*log(v) or e*log(v).

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        it is $$$\mathcal{O}(E\cdot\log(V))$$$ but $$$E \in \mathcal{O}(V^2)$$$

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can actually do $$$O(|V|^2)$$$ if $$$|E|$$$ is large. In every vertex you find the closest just by iterating through all vertices, and forget about the priority queue.

      Another option is using fibonacci heap instead of standard binary heap, which gives $$$O(|E| + |V|log|V|)$$$.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Your first point is true. But that is worse than the time complexity that I described in general because you have to make VERY dense graphs for your algo to be useful.

        Also, while fibonacci heap can indeed speed up the runtime of dijkstra's algo, I think that it is a common understanding that dijkstra's algo uses binary heap.

        Just like dicnic's algo, you can speed it up using LCT, capacity scaling and all, but we still stick with the one which is commonly taught in academia.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Even thought fibonacci heaps are theoretically faster, there constant factor is so big that in practice a binary heap is always faster (atleast this holds for real world road networks... but in my tests this also holds for other graphs).

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

can we do better than O(|V|)?

What are you talking about? Lol. Take any deterministic path finding/shortest path algo. We can always make it traverse the entire graph for ANY given graph. I am lazy to provide a proof but you can easily prove it by induction. Anyway, without going into further details, just consider the case where we have a line graph. Now set your source and destination to be the ends of the graph. Your algo has no choice but to traverse all vertices of the graph.

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Your algorithm is wrong.

(1, 2) w = 4
(1, 3) w = 1
(3, 2) w = 1
(2, 4) w = 1

the shortest path from 1 to 4 las length 3 but your algorithm will say its 5...

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh can you say what is wrong in my algorithm?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      You are using a queue instead of heap so you are not taking into considerations the weights. What you do, would work in unweighted graphs, because what you are really doing is BFS.

      You set node u as "visited" the first time you visit it. But maybe in the future you will find a shortest path that pass through u and leads to a better solution for an other node v. So to fix your solution, you should include node "u" to the queue every time you find a shortest path to u. But this will lead to O(n^2), so this is why we use Dijkstra's algorithm with heap.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        But maybe in the future you will find a shortest path that pass through u and leads to a better solution for the other node v Hi I didn't understand why is that?

        If we can go to a better place from u at later times then at first we can go to because we are visiting all of the neighbors of u.

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Username checks out