Dijkstra's Algorithm

An Implementation of the shortest-distance algorithm built in C++ for Windows

Purpose

The purpose of Dijkstra's Algorithm is to find the shortest distance between any two given nodes in a graph. This is very appropriate for optimizing systems where entering one state from another comes at a cost.

Downloading and Installing the Program

Download the Windows installer zip file by clicking the button below. After downloading the zip file, unzip the folder. Then double-click the "setup" file to begin installation. Follow the directions on the installation wizard to complete the installation process.

Windows Installer

Using the Program

On startup, the program prompts for names of each node. After entering each node name, type "done" to finish entering the names. Then, the program will ask the user if they want a digraph (where each distance is one-way) or an undirected graph (where each distance is two-way). After this, the program will prompt the user for the distance between each node. To represent no connection between nodes, type "i" or "infinity" instead of a number. Once this is finished, the program outputs the shortest distance between each node for every possible combination of nodes. Additionally, the path that must be followed to achieve the shortest distance for each case is printed. At the end, the user can choose to start over with a different graph (set of nodes) or exit the program.

Top-Level Implementation

The graph is implemented as a vector of nodes, where a node is a struct defined as follows:

struct node{
    vector <float> direct_distance;     // direct_distance[i] is direct distance from current node to node i
    vector <float> dijkstra_distance;   // dijkstra_distance[i] is shortest distance from current node to node i
    vector <string> dijkstra_path;      // dijkstra_path[i] is the shortest path from current node to node i (as a string)
    string name;                        // name of the node
};

Repository

The entire C++ source code along with a Linux implementation can be found in this GitHub repository.