/bnw-implementation

An implementation of the Bernstein-Nanongkai-Wulff-Nilsen Algorithm (2022) for single-source shortest paths with negative edge weights

Primary LanguageJupyter Notebook

CS 270 Final Project

This repository provides code implementations of the following single-source shortest paths algorithms:

  • BNW
  • Bellman-Ford
  • Dijkstra's

This project was developed by Youngjin Park, Jonny Pei, and Vivek Verma.

Setup/Installation

  1. Install the latest version of Python. We developed our code and ran experiments using Python 3.9.7, but any slightly older/newer version should work fine.

  2. Clone this repo and move into it.

git clone https://github.com/vivek3141/cs270-final-project.git
cd cs270-final-project
  1. Install the required packages.
pip install -r requirements.txt
  1. Install the repo.
pip install -e .