The downloads below provide a package containing all of the main algorithm repository's C source files.
A separate section of this repository specialises in shortest path algorithms and priority queues implemented in C++.
All algorithms and source files provided by this repository are subject to the disclaimer below.*
Depth First Search and Breadth First Search
Tarjan's Algorithm (Strongly Connected Components)
Dijkstra's Algorithm
Two implementations are given which differ by the data structure used for the frontier set.
Implemented with a one-dimentional array:
Implemented with a heap:
Floyd's Algorithm
Minimal Spanning Tree Algorithms
Currently only Prim's minimal spanning tree algorithm is implemented.
Maximum Flow Algorithms
The Ford and Fulkerson, Dinic, MPM, and Karzonov maximum flow algorithms are implemented.
Some CPU time data is available for a performance comparison of functions in sort.c, and the qsort() function provided by the C header <stdlib.h>.
Quicksort
Mergesort
Radix Sort
Heap Sort
Currently only binary search is implemented.
Convex Hulls
An implementation of Graham's scan for simple 2-dimensional convex hulls.
Common Files
A description of all the heaps implemented is provided.
The header file heap_info.h defines a common structure type for heaps so that they can be used interchangeably. A program which uses this common structure type is then able to use different heaps interchangeably. The heap implementation of Dijkstra's algorithm is an example of this.
Binary Heap
Fibonacci Heap
2-3 Heap
The trees in a 2-3 heap can be viewed in two different ways, and this leads to two different 2-3 heap implementations.
Implemented using linked lists of child nodes:
Implemented using linked lists of child node-pairs:
In the node-pair implementation the linked list of child nodes is defined differently. Nodes have an extra pointer which points to an optional partner node with which the node forms a node-pair. Each node has a boolean field which identifies whether it is the "extra" node a node-pair.
Trinomial heap
The extended trinomial heap implementation supports O(1) worst case time for decrease_key:
The basic trinomial heap implementation supports O(1) amortized time for decrease_key:
Common Files
The header file dict_info.h defines a common structure type that each dictionary can provide. A program which uses this common structure type is then able to use different dictionaries interchangeably, as done by the supplied example program.
Binary Search Tree
AVL Tree
2-3 Tree
Standard 2-3 tree:
Modified 2-3 tree, supporting delete_min() in O(1) worst case time:
Red-Black Tree
Hash Table
Skip List
Digital Search Tree
Radix Search Trie
This secondary repository contains C++ implementations of shortest path algorithms and the priority queues that they use. A standard implementation of Dijkstra's algorithm is provided which is able to use the various priority queues interchangeably.
A standard implementation of directed graphs is used by Dijkstra's algorithm.
Various heaps for use in Dijkstra's algorithm are provided. These are all derived from a common base class.
The individual heap implementations are given below:
Since the radix heap works specifically with Dijkstra's algorithm, it is described separately from the other heaps. A description of other heaps can be found in the heaps section of the main algorithm repository
Dijkstra's algorithm was implemented with the ability to use any of the above heaps.
Example Usage (Experiment Code)
The following example program demonstrates how to use the different heap implementations with Dijkstra's algorithm.
In addition, the following experiment code can be used to compare the different instances of Dijkstra's algorithm on different graphs.
Files may only be downloaded in acceptance with the disclaimer.*
The entire algorithm repository source code and makefiles can be downloaded as a single package containing the directory structure expected by the source files. Alternatively, individual parts of the algorithm repository are available as separate packages. Individual C source files are viewable from the algorithm repository web pages. A README file is available, which gives an outline of source files in this repository and the directory structure used.
Algorithms
Data Structures
Related
*Disclaimer: You agree that this repository contains non-commercially developed algorithms and that the source code and related files may contain errors. In no event will the provider of this repository be held responsible for any damages resulting from the source code and related files supplied by this repository or the use thereof. You acknowledge that you use all source code and related files supplied by this repository at you own risk.
