Graph Algorithms

A collection of some graph algorithms I wrote during my free time
They all contain pretty in-deaph comments, so feel free to use as refrence
Some of these were homework for my ALGO2 Class

Algorithms:

• Advanced Pathfinding Algorithms

  • Dijkstra’s algorithm (Done!)
    • Used to find smallest path from one node to any other node with non-negative weigth on vertices. Some examples of its usage could be google maps to find shortest route.
  • Bellman-Ford’s algorithm (Done!)
    • Similar to Dikjtra, but it can handle negative weigths. In return, it detect nagative cycles.

• All Pairs Shortest Path Algorithms

  • Floyd-Warshall’s algorithm (Done!)
    • Used to find shortest path from all nodes to all other nodes (All Pair Shortest Paths (APSP))

• Advanced Minimum Spanning Tree Algorithms

  • Kruskal’s algorithm (Done!)
    • Used to find minimun spanning tree (MST). It calculates shortest route that passes througth all nodes.
  • Prim’s algorithm (Done!)
    • Used to find minimun spanning tree (MST), similar to Kruskals. Major difference is Prim scans by nodes, while Kruskals scans by verticies.

• Maximum Flow Algorithms

  • Ford-Fulkerson algorithm (TODO)
    • Description TODO
  • Dinic's algorithm (TODO)
    • Description TODO