Dijkstra's algorithm: Computes shortest paths in a graph with non-negative edge weights.
Floyd-Warshall: Solves the all pairs shortest path problem in a weighted, directed graph.
Prim: Finds a minimum spanning tree for a graph.
Kruskal: Finds a minimum spanning tree for a graph.
Boruvka: Finds a minimum spanning tree for a graph.
Johnson: All pairs shortest path algorithm in sparse weighted directed graph.
Ford-Fulkerson: Computes the maximum flow in a graph.
Edmonds-Karp: Implementation of Ford-Fulkerson.
Bellman-Ford: Computes shortest paths in a weighted graph (where some of the edge weights may be negative).
Hungarian: Algorithm for finding a perfect matching.
Coloring algorithm: Graph coloring algorithm.
Topological sort: Sort a directed acyclic graph in such a manner that each node comes before all nodes to which it has edges (according to directions).
Nearest neighbour: Find nearest neighbour (Travelling salesmen problem).
Tarjan's off-line least common ancestors algorithm: Compute lowest common ancestors for pairs of nodes in a tree.
For more graph theory algorithms, please visit this.
Dijkstra's Algorithm Runtime:
No comments:
Post a Comment