noobied's blog

Dijikstra !!
By noobied, history, 6 years ago, In English

How this Solution works even if in priority queue the values stored are not weights.I think for Dijikstra to work we should maintain a priority queue which give the node whose distance is shortest from the source but in this implementation the priority queue gives the smallest node number

LINK:http://codeforces.net/contest/20/submission/30960352

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it -15 Vote: I do not like it

PLZZ HELP ME UNDERSTAND THIS SOLUTION AND IF I CHANGE THE PRIORITY QUEUE TO QUEUE IT GIVE TLE AT TEST NUMBER 28 I DIDN'T ABLE TO UNDERSTAND HOW PRIORITY QUEUE IS BENIFICIAL HERE INSTEAD OF A NORMAL QUEUE

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

    To begin with ,Dijkstra algorithm is a Greedy Algorithm.

    Therefore while using Dijkstra algorithm we have to use a priority queue (or similar data structure ) so that we can process the edge which have greater weight's before the edges that have a smaller weight.

    Reason for doing so :

    "if(dis[u] + w < dis[v])" this particular statement check's if the previous path has more weight than the current path. If we process the heavier edges first then this process becomes very much easier.

    That is the reason for using priority queue in Dijkstra.

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

      But the code store the node number instead of wieghts in the priority queue

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        In the question you are trying to solve , The author's solution is just storing the neighboring nodes.

        If u check TC # 28 , if you do not use a priority queue , u will have to process 50000 nodes. but using priority queue , 50000 will be above all the other nodes.

        And also there is a direct path from node 1 to node 50000.

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

          In the originally linked solution, how does the priority queue know which nodes are closest (and thus should be processed first) when the priority queue only stores the node (instead of say, a pair<node, weight>)?

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            yes thats my question REDUX.There should be weight stored too along with the node number

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the problem might have weak test case, and the TL is too tight for priority queue to pass (because of doubled runtime).

Counter case:

5 5
1 2 1
2 3 1
1 4 10
4 5 1
1 5 5

The linked code (and my own "AC" solution) prints "1 5" instead of "1 2 3 4 5".

→ Reply