Johnson’s algorithm for sparse graphs writed in C referrering to chapter 25.3 of CLRS (Introduction To Algorithm). The Dijkstra algorithm is implemented with binomial heap using bheap_decrease_special() instead of bheap_decrease().

 

program list:

graph.c

　　universal graph which can be directed or undirected using adjacency list.

　　contains a struct to represent the shortest path of a single-source.

bheap.c

　　binomial heap and its operation.

Bellman-Ford.c

　　Bellman-Ford algorithm.

Dijkstra.c

　　Dijkstra algorithm using binomial heap, and using bheap_decrease_special() instead of bheap_decrease().

Johnson.c

　　Johnson  algorithm by using Bellman-Ford algorithm and Dijkstra  algorithm.

　　contains a short test case same as Figure25.1 on CLRS.