DaviddeGea1's blog

By DaviddeGea1, history, 4 weeks ago, In English,

I get really confused at times at to which graph algorithms is specific to directed(or undirected) graphs or can be applied to both. So just wanted to create a blog that will contain all the graphs algorithms and their area of application(Directed, undirected or both).

I'll start with some about which I'm sure of:

  • DFS, BFS : Both

  • Topo sorting : Directed

  • Dijkstra : Both

  • Prims, Kruskal : Both

Please add more algorithms and/or correct me if I'm wrong.!

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Screenshot-12

For Directed Graphs this info is useful for selecting a particular algo.
Source: Competitive programming 3 by Steven Halim.
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    how did they make dijkstra work for negative weights?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They probably mean dijkstra with potentials

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give an explanation? I can't find anything good on google.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          link

          It's typically used in min-cost-max-flow. In that case the initial potentials are 0 and you just add the distance to vertex potential (if I remember that right) after the Dijkstra run.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If they have to use bellman-ford to get the metagraph then wouldn't it still be O(VE)?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              Idk, I found the source, the Dijkstra on 148 page is just the regular one and Exercise 4.4.3.2* on page 150 hints it does not really work (in $$$O((V + E)logV)$$$) for negative weights iiuc. At least $$$O(V(V + E)logV)$$$ (I can construct that).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      download!

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 4   Vote: I like it +3 Vote: I do not like it

      In order to make Dijkstra's algo work for negative weights, you have to push nodes into the priority queue whenever an edge is relaxed. But this may lead to multiple copies of a single vertex (with different distance info) being pushed into the priority queue. So, you will need to check if the distance of the node that you just removed from the priority queue is == optimal distance calculated for that node. If the condition is true, you use the node. Otherwise, you discard it.

      Unfortunately, this modified version of Dijkstra's algo has exponential runtime in the worst case (for graphs with -ve weights) and it doesn't terminate on graphs with -ve cycles. But the type of graphs that can force the exponential behavior occur very rarely so it is quite safe to use it.

      Just in case you are interested, here is the link to Dr Halim's modified dijkstra's algo and here is the worst case graph. Click on Example graphs > Dijkstra's Killer.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Want to add: topological sort can only be used with directed acyclic graph(DAG).