Some algorithms implemented in C.

Computes shortest paths from a single source to all other vertices in a weighted directed graph.

./a.out <input file> <source>

input file: line1: number of vertices, line2~n: adjacency matrix of the graph.
source: the source vertice.

This will save a bellman_ford_out.txt file to the directory.

Find maximum sub-array in an array.

./a.out

elements: the size of the randomly generated array

Also provide an optimized version.

Computes shortest paths between all pairs of vertices in a sparse, edge weighted, directed graph.

The algorithm works as this:

1. add a node q to the graph, connected by zero-weight edges to each of the other nodes.
2. do bellman ford algorithm from source q, resulting h(v) of a path from q to v. Terminate if negative weight cycle is found.
3. reweight the graph by w(u, v)' = w(u, v) + h(u) - h(v)
4. remove q and do dijkstra algorithm to find the shortest paths from each node s to every other vertex in the reweighted graph.

./a.out <input file>

input file: line1: number of vertices, line2: number of edges, line3~n: .

This will save a johnson_out.txt file to the directory.

Counts how many inversions used in a merge sort.

./a.out

10 numbers: give an array.

The classic N-Queen problem.

Computes the optimal binary search tree given probabilities pi and qj.

./a.out <input file>

input file: line1: (node 1, probability p1) (node 2, proba...), line2: (dummy keys 0, probability q0) (dummy keys 1, proba...)

This will save a optimal_bst_out.txt file to the directory.

Construct a prefix code based on a set of symbols and their probabilities.

./a.out

8 elements: number in sorted order