Dijkstra Implementation

CS400: Programming III

Taught by Prof. Gary Dahl

Project Overview

This Java project implements a version of Dijkstra's shortest path algorithm tailored for graphs represented by nodes and edges with weights. The DijkstraGraph class extends a BaseGraph data structure and utilizes priority queues to efficiently find the shortest path between two nodes.

Features

Compute Shortest Path: Determine the shortest path from a starting node to an ending node, including the path's total cost.
Path Retrieval: Retrieve the list of node data along the shortest path.
Exception Handling: Properly handles cases where no path exists between the specified nodes.

Graph visualization representing Dijkstra's algorithm — Visual representation of Dijkstra's Algorithm illustrating the shortest path calculation between nodes

Getting Started

Prerequisites

Java JDK 11 or later.
JUnit 5 for running unit tests.

Running the Project

Download the File:
DijkstraGraph.java
Compile the Java files using javac:
```
javac DijkstraGraph.java
```
Run the compiled classes using java:
```
java DijkstraGraph
```

Usage Example

To use this library, create an instance of the DijkstraGraph, add nodes and edges, and then query for the shortest path:

DijkstraGraph<String, Double> graph = new DijkstraGraph<>();
graph.insertNode("A");
graph.insertNode("B");
graph.insertNode("C");
graph.insertEdge("A", "B", 1.0);
graph.insertEdge("B", "C", 2.0);

List<String> path = graph.shortestPathData("A", "C");
double cost = graph.shortestPathCost("A", "C");
System.out.println("Path: " + path);
System.out.println("Cost: " + cost);

Running Tests

To execute the tests, run:

java org.junit.runner.JUnitCore DijkstraGraphTest

License

Distributed under the MIT License. SeeLICENSE.txt for more information.