Floyd-Warshall-Algorithm

KO | EN

gitlite — search

#typescript #ai-agents #deepseek-harness #dsh-plugin #open-source #ai #cli #dsh #claude-code #codex #developer-tools #react

Floyd-Warshall-Algorithm

★ 1 Open GitHub ↗

Recursive and iterative implementations of the Floyd-Warshall shortest path algorithm with benchmarking, unit testing and Sphinx documentation.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Floyd-Warshall Recursive Implementation

## Overview

This project investigates a recursive reformulation of the Floyd-Warshall algorithm, a dynamic programming technique used to compute the shortest paths between all pairs of nodes in a weighted graph.

The traditional Floyd-Warshall algorithm is typically implemented using three nested loops. The primary objective of this project is to replace those loops with a recursive formulation while preserving correctness and compare the performance of the recursive and iterative approaches through automated benchmarking.

The project also includes unit testing, performance benchmarking, defensive input validation, and generated technical documentation.

Developed as part of the MSc Computer Science programme at the University of Liverpool.

---

## Features

* Recursive Floyd-Warshall implementation
* Iterative Floyd-Warshall implementation
* Defensive validation for invalid graph inputs
* Automated unit testing using `unittest`
* Performance benchmarking
* Sphinx-generated documentation
* Git hooks for linting, testing and commit message validation

---

## Project Structure

```text
src/
├── iterative/
├── recursion/
└── tests/

docs/
└── source/

report/
└── Floyd_Warshall_Report.pdf
```

---

## Installation

Create and activate a virtual environment:

```bash
conda create -n floyd-env python=3.14
conda activate floyd-env
```

Install the project dependencies:

```bash
pip install -r requirements.txt
```

---

## Running the Project

### Run the recursive implementation

```bash
python -m src.recursion.recursive_floyd
```

### Run the iterative implementation

```bash
python -m src.iterative.iterative_floyd
```

### Run the unit tests

```bash
python -m unittest -v src.tests.unittests
```

### Run the performance comparison

```bash
python -m src.tests.performance_test
```

---

## Benchmark Results

Benchmarking was performed across 10 trials, with each implementation executed 10,000 times per trial.

| Implementation | Mean Time (s) | Standard Deviation (s) |
| -------------- | ------------: | ---------------------: |
| Recursive      |         0.379 |                 0.0607 |
| Iterative      |         0.307 |                 0.0228 |

For the full benchmarking methodology, raw timing results, statistical analysis, and evaluation, see the project report located in:

```text
report/Floyd_Warshall_Report.pdf
```

---

## Documentation

Detailed project documentation is available through Sphinx.

Build the documentation:

```bash
cd docs
.\make.bat html
```

The generated documentation can then be opened from:

```text
docs/build/html/index.html
```

The documentation includes:

* Project overview
* Algorithm summary
* Testing methodology
* Performance benchmarking methodology
* API reference

---

## Academic Report

A detailed report describing the design, implementation, testing strategy, and performance evaluation of the recursive Floyd-Warshall algorithm is included in:

```text
report/Floyd_Warshall_Algorithm_Report.pdf
```

The report covers:

* Algorithm design decisions
* Recursive formulation of Floyd-Warshall
* Validation strategy
* Unit testing approach
* Performance benchmarking
* Comparison of recursive and iterative implementations
* Evaluation of results

---

## Development Workflow

This repository uses Git hooks to enforce development standards before each commit:

* Ruff linting checks
* Automated unit test execution
* Commit message validation

Example commit message:

```text
Project: Add Git hooks and repository cleanup.
```

---

## Technologies Used

* Python
* Dynamic Programming
* unittest
* Ruff
* Sphinx
* Git
* Git Hooks

---

## Skills Demonstrated

* Algorithm design
* Dynamic programming
* Recursion
* Defensive programming
* Software testing
* Performance benchmarking
* Technical documentation
* Version control and development workflows

Floyd-Warshall-Algorithm

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README