Implementation of well known algorithms, mainly graphs and sorting, in python
These algorithms are listed below in alphabetical order:
##All Pairs Shortest Path - Bellman-Ford, the algorithm for single source shortest path is used in a loop over all vertices, along with the usual APSP algorithms - Floyd-Warshall and Johnson's.
Depth-first-search and breadth-first-search.
Counting the number of inversions in an array.
It is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.
Numerous variants of Quicksort.
The randomized contraction algorithm to compute number of Minimum cuts in a graph.
This problem can be solved by several graph search algorithms - most notable among them - Djikstra and Bellman-Ford, which are implemented. Djikstra, the faster algorithm, is used for graphs with non-negative edge costs, while Bellman-Ford, the slower algorithm is used for graphs with any edge costs.
Kruskal's Minimum Spanning Tree algorithm and Single-Link Clustering algorithm are implemented with multiple variants of the Union-Find data structure and also without using the Union-Find.
In all cases, the times taken by the algorithms to run are reported. The individual folders also have Readme files which contain details about these implementations.