This algorithm project focuses on the implementation and formal analysis of the Floyd–Warshall algorithm to solve the all-pairs shortest path problem. It demonstrates the power of dynamic programming in optimizing pathfinding within complex, weighted directed graphs. This project features:

• Dynamic Programming: Implemented the Floyd–Warshall algorithm in Java to compute shortest paths across all vertex pairs.
• Graph Processing: Developed logic to handle adjacency matrices with support for infinite edge weights and up to 25 vertices.
• Iterative Relaxation: Computed and displayed the transformation of the distance matrix D(n) after each relaxation step.
• Complexity Analysis: Applied formal runtime analysis using Big O notation to evaluate the O(n³) time complexity.
• Validation: Verified 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: Mastery of Selection, Bubble, Insertion, Merge, Heap, and Quick Sort algorithms.
• Graph Theory: Implementation of Breadth-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.