BanazadehAria's blog

By BanazadehAria, history, 5 years ago, In English

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];
}
  • Vote: I like it
  • -15
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh can you say what is wrong in my algorithm?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Username checks out