Floyd Warshall Shortest Path Algorithm Analysis

Requirements

Requires some form of C++ compliation; preferably g++.

Usage

• Invoke the make command to create an executable called floydWarshall.exe
• Run the executable with..
  • ./floydWarshall [inputSize] [true/false]
  • Where inputSize is the size of the weighted graph
  • True for more dense graphs and false for more sparse graphs
• Runs 2 implementations (one optimized) of the Floyd Warshall Algorithm with random weights and outputs the average run times of both

Concepts and Languages Used

• How Floyd Washshall is performed and where optimizations could be made.
• C++ was used because it is a high level language I felt comfortable using.
• Timing the performance of algorithms in C++ using high-resolution clock.