This algorithm project for CST370: Design and Analysis of Algorithms focuses on the implementation and formal analysis of the Floyd–Warshall algorithm to solve the all-pairs shortest path problem. I explored how dynamic programming can optimize pathfinding within complex, weighted directed graphs. This project features:
- Dynamic Programming: Implementing the Floyd–Warshall algorithm in Java to compute shortest paths across all vertex pairs.
- Graph Processing: Developing logic to handle adjacency matrices with support for infinite edge weights.
- Iterative Relaxation: Computing and displaying the transformation of the distance matrix D(n) after each relaxation step.
- Complexity Analysis: Applying formal runtime analysis using Big O notation to evaluate efficiency.
- Validation: Verifying algorithm correctness using multiple sample test cases and edge-case graph topologies.
Additional Topics Covered
Beyond shortest path algorithms, this course involved a comprehensive study of fundamental computer science concepts:
- Sorting & Searching: Selection, Bubble, Insertion, Merge, Heap, and Quick Sort algorithms.
- Graph Theory: bread-First Search (BFS), Depth-First Search (DFS), and Prim’s Algorithm for Minimum Spanning Trees.
- Design Paradigms: Exploration of Decrease-and-Conquer, Divide-and-Conquer, and Transform-and-Conquer strategies.
- Formal Analysis: Using Big O, Big Theta, and Big Omega notations to define algorithm efficiency bounds.
The project and coursework demonstrate a strong foundation in designing efficient solutions to complex computational problems. Computational efficiency is as much about choosing the right algorithmic paradigm as it is about writing clean code.
Project Deliverables
- Source Code: Available upon request (Classroom Project)