Pathfinder

Date: October 2024.

Pathfinder is a program in C that finds all the shortest paths between all the islands, using information about the bridges which connect them. The project was developed during Track C, the second stage of the Innovation Campus educational program.

The program:

• reads data from a file specified as a command-line argument;
• finds all the shortest paths between each combination of two islands using the Dijkstra’s algorithm;
• prints the paths using the FIFO rule for the islands to the stdout.

Note that not all used functions are shown here, but only those developed specifically for Pathfinder. The program uses many functions from my library Libmx, developed in the previous assignment.

Installation

To compile the program, clone the repository, navigate to the project directory, initialize and update libmx submodule and build the project using make command.

git clone https://github.com/VeronikaSukhonos/pathfinder
cd pathfinder
git submodule update --init
make

This will first compile a static library libmx in its directory and then create an executable binary file pathfinder in the project directory.

Usage

Input file:

The first line is the number of islands, and remaining lines describe the distance between the two islands, one per line, in a format:

island1-island2,length_of_bridge\n

Note that:

• the names of the islands must contain only alphabetic characters, cannot be empty or identical;
• the first line and the length of the bridge must contain only digits (a positive value) and cannot be empty;
• the sum of the lengths of all bridges must not exceed INT_MAX

Running the program:

./pathfinder [filename]

Example input:

5
A-B,11
A-C,10
B-D,5
C-D,6
C-E,15
D-E,4

Example output:

========================================
Path: A -> B
Route: A -> B
Distance: 11
========================================
========================================
Path: A -> C
Route: A -> C
Distance: 10
========================================
========================================
Path: A -> D
Route: A -> B -> D
Distance: 11 + 5 = 16
========================================
========================================
Path: A -> D
Route: A -> C -> D
Distance: 10 + 6 = 16
========================================
========================================
Path: A -> E
Route: A -> B -> D -> E
Distance: 11 + 5 + 4 = 20
========================================
========================================
Path: A -> E
Route: A -> C -> D -> E
Distance: 10 + 6 + 4 = 20
========================================
========================================
Path: B -> C
Route: B -> D -> C
Distance: 5 + 6 = 11
========================================
========================================
Path: B -> D
Route: B -> D
Distance: 5
========================================
========================================
Path: B -> E
Route: B -> D -> E
Distance: 5 + 4 = 9
========================================
========================================
Path: C -> D
Route: C -> D
Distance: 6
========================================
========================================
Path: C -> E
Route: C -> D -> E
Distance: 6 + 4 = 10
========================================
========================================
Path: D -> E
Route: D -> E
Distance: 4
========================================

Possible errors

You may get the following errors if:

• there is an invalid number of command-line arguments

usage: ./pathfinder [filename]

• the file does not exist or it is empty

error: file [filename] does not exist

error: file [filename] is empty

• one of the lines does not match the format

error: line [line_number] is not valid

• the number from the first line does not match with the real number of islands

error: invalid number of islands

• there is more than one bridge between the islands

error: duplicate bridges

• the sum of the lengths of all bridges in the file exceeds INT_MAX

error: sum of bridges lengths is too big

License

The project is licensed under the terms of the MIT license. See the LICENSE file for details.