Neftaly: Observing Floyd-Warshall Efficiency

This Neftaly activity focuses on exploring the efficiency of the Floyd-Warshall algorithm, a fundamental graph algorithm used to compute shortest paths between all pairs of vertices in a weighted graph. The algorithm is particularly valuable in computer science, networking, and operations research, as it provides a systematic method for determining shortest paths even when negative edge weights exist, provided there are no negative cycles. By observing the efficiency of Floyd-Warshall, learners gain practical insights into algorithmic performance, computational complexity, and real-world applicability.

In this activity, learners are introduced to the Floyd-Warshall algorithm’s core principles. The algorithm employs a dynamic programming approach, iteratively improving the shortest path estimates by considering each vertex as an intermediate node. Learners study how the adjacency matrix representation of a graph is updated over multiple iterations and how intermediate computations lead to the final shortest-path results. By examining step-by-step updates, learners can visualize how the algorithm processes information and reduces path distances efficiently.

The activity involves hands-on experimentation with graphs of various sizes and complexities. Learners implement the Floyd-Warshall algorithm in programming languages such as Python, Java, or C++ and measure performance metrics including execution time, memory usage, and number of operations. They observe how graph size, edge density, and weight distribution affect algorithm efficiency.