Understanding All-Source Shortest Path Calculations
Finding the shortest path between every pair of vertices in an edge-weighted directed graph is a fundamental problem in computer science and discrete mathematics. Unlike single-source algorithms like Dijkstra's, all-source algorithms compute paths between all possible node combinations simultaneously. This calculator utilizes optimized matrix multiplication principles and dynamic programming frameworks to evaluate complete graph topologies efficiently.
Formula Used
The core computational engine is built upon the classic dynamic programming recurrence relation popularized by Robert Floyd and Stephen Warshall. The distance matrix update rule at step $k$ is defined formally as:
$$D^{(k)}(i, j) = \min\left(D^{(k-1)}(i, j), \, D^{(k-1)}(i, k) + D^{(k-1)}(k, j)\right)$$
Where $D(i,j)$ represents the shortest distance from vertex $i$ to vertex $j$, and intermediate vertex $k$ acts as an optional stepping stone to check if a shorter composite route exists.
How to Use This Calculator
- Define Node Size: Select your desired total node count ranging from 2 up to 8 vertices.
- Input Adjacency Matrix: Enter row values separated by commas, typing
INFwhere no direct connection exists. - Select Algorithm Preferences: Choose between standard evaluations or negative weight checking matrices.
- Submit and Review: Click the calculate button to review computed matrices directly above the form interface.
Frequently Asked Questions
What does INF mean? INF signifies infinity, indicating that no direct edge connects those specific nodes.
Can I use negative numbers? Yes, configure the negative weight setting to enable detection routines for cyclical loops.