Graph algorithms implementations

Implementations of four graph algorithms: Dijkstra's and Bellman-Ford's shortest path plus Prim's and Kruskal's minimum spanning tree and for the course COMP369 - Teoria dos Grafos (Graph theory).

---

Input file format

The input file format is as follows:

<vertex_count> <edge_count>
<edge_1_start> <edge_1_end> <edge_1_weight>
<edge_2_start> <edge_2_end> <edge_2_weight>
...
<edge_n_start> <edge_n_end> <edge_n_weight>

---

Checklists

Done:

• Dijkstra's shortest path
• Prim's minimum spanning tree
• Kruskal's minimum spanning tree
• Heap optimization using an auxiliary array to track where each vertex is currently at the heap to enable O(1) weight update
• Bellman-Ford's shortest path

To do:

---

Algorithms' usage

To build all algorithms:

make

This will build all algorithms and move them to the root directory named as dj, bf, pr and kr.

Dijkstra's and Bellman-Ford's Shortest Path

To build and run Dijkstra's:

cd dijkstra
make
./dijkstra <options>

To build and run Bellman-Ford's:

cd bellman-ford
make
./bellman-ford <options>

Options:

-h              : displays this help and exits
-o <file>       : redirects output to file
-f <file>       : indicates the file that contains the graph 
-i              : starting vertex. default: 1

Prim's and Kruskal's Minimum Spanning Tree

To build and run Prim's:

cd prim
make
./prim <options>

To build and run Kruskal's:

cd kruskal
make
./kruskal <options>

Options:

-h              : displays this help and exits
-o <file>       : redirects output to file
-f <file>       : indicates the file that contains the graph 
-s              : prints all edges of the resultant MSP instead of it's cost
-i              : starting vertex. default: 1

---

Author

• Victor Alexandre da R. Monteiro Miranda - 📧 varm@ic.ufal.br