I-dont-know-FFT's blog

Help needed in Dijkstra
By I-dont-know-FFT, history, 23 months ago, In English

" Dijkstra works when distance/cost is monotonic i.e all positive edges or all negative edges. But there shouldn't be any negative cycles "

can some make me understand the negative edges part , Thanks :D

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

negative cycles mean that there is some cycles whose cost (sum of composing edges) is negative. There shouldnt be such negative edges because then the algorithm does not make sense (the cost to get from A to B is negatively infinite as you can go through that cycle for as long as you want, making the cost infinitely small, and if you want, at some point you can leave the cycle and go towards B (but you could've still made the cost smaller by continuing on the cycle))

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    One correction here, there can be negative edges in the graph for dijkstra to work, but in case of negative cycle, it will go into an infinite loop.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No i think this is wrong. If negative edges exist in the graph, the dijkstra's algorithm doesn't work. This is because dijkstra's algorithm is based on a greedy assumption that does not hold true when negative edges exist.

      Also, dijkstra never goes into an infinite loop in any circumstance, even when there are negative cycles. Dijkstra always runs in O((n+m)logn) time. This is because dijkstra will never visit vertices which have already been visited.

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I think you need to get your facts right. You can refer to this article from GFG. Dijkstra may work in some cases where there is a negative edge but not in all of them.

        Eg : Consider a loop like this in a graph with three nodes A, B and C : A->B->C->A.

        Assume :

        • A -> B has weight -1.

        • B -> C has weight 5.

        • C -> A has weight 4.

        Here Dijkstra will work perfectly fine as the cycle has a positive cumulative weight.

        For the second part (about the infinite loop) you can refer this.

        Hope this helps.

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          An algorithm is only considered correct if it works in every testcase. Therefore, i am still correct in saying that dijkstras algorithm doesnt work when u have a negative edge.

          as for the negative cycle, it depends on your implementation of dijkstras. When i implement it, i make sure that i never visit the same vertex twice so i will never enter an infinite loop.

          However, the conclusion still remains that when negative edges exist, dijkstras algorithm is incorrect.

          → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Also, just to clarify, are you saying that if a graph has negative edges but only positive cycles then dijkstras algorithm will work? If so then that is incorrect as well. And if u want an example, it exists in the second link that u posted urself

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            I think you haven't read my reply correctly. I clearly mentioned Dijkstra may work in some cases where there is a negative edge but not in all of them. Try reading the reply again.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              I know what u said man. But what ur not understanding is that if it doesnt work in some cases then it doesnt work at all. I know that it may be hard for u to wrap ur head around that but thats how algorithms work. Unless it works in every testcase and every scenario, it may as well be useless.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                23 months ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                Got your point bro. I just tried to explain the statement in the blog

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              When ur doing a contest, do u try to make an algorithm which always works or sometimes works? U will obviously try to make an algorithm which always works becos if it doesnt always work then ur code will produce a wrong answer in one of the testcases and u wont get any points. So if its not correct in every testcase, then it isnt correct at all. Thats all im saying

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

                (https://cses.fi/problemset/task/1680) [In this problem, I converted all edge weights to -1 and performed a Dijkstra it gave correct ans , upon searching about it I came across this statement , that Dijkstra require monotonic edge weights (either all positive edges or all negative edges, also no cycle.] [Solution](https://pastebin.com/yn6A9RJ2)

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

                  Here Dijkstra worked because there were no directed cycles i.e. no negative cycles as I mentioned above.

                  So using -1 as edge weight will return maximum distance instead of minimum.

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

                  It's interesting because even though you are right that dijkstra will correctly calculate maximum distance instead of minimum, if im not wrong, then time complexity of dijkstra will no longer be O((n+m)logn). Instead, in specific testcases, i think it will go up to O(n*(n+m)logn). basically multiplying by an additional factor of n. Pls respond if you want explanation of why i think this is the case.

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

                  I think we should use simple BFS instead of Dijkstra because all edge weights are the same.

                  That will run in much lesser time complexity.

                  And I think you are right.

                  → Reply