DaviddeGea1's blog

Directed and Un-directed graphs algorithms
By DaviddeGea1, history, 5 years 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

Comments Comments (9)
| Write comment?
»
5 years 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.
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    how did they make dijkstra work for negative weights?

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

      They probably mean dijkstra with potentials

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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)?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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).

              → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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).

→ Reply