Floyd-Warshall Algorithm

Problem

Given the number of nodes n, directed edge information in edges, and query details in query, write a solution function that returns the length of the path from the start node to the end node for each query.

Assume that the graph has no negative cycles and that each node can reach every other node.

Concept Explanation

The Floyd-Warshall Algorithm is used to find the shortest paths between any two nodes in a graph. It is applicable to graphs with negative edge weights. When a negative cycle exists, it can detect this as the shortest distance may approach negative infinity, indicating the presence of a negative cycle.

Assume a directed edge graph is given as below.
Define the path length from a node to another node as D[i][j].

D[i][j] is updated to the shortest path length by considering paths passing through other nodes.
The update formula is $D[i][j] = min(D[i][j], D[i][k]+D[k][j])$. Starting from k=1, the updated result is as follows:

When k=2, the updated result is:

When k=3, the updated result is:

When k=4, the updated result is:

After iterating through all nodes for k, the shortest path from node i to node j is stored in D[i][j].
If D[i][i] for any node is negative, a negative cycle exists, and if D[i][j]=INF for any i, j, node j is unreachable from node i.

Constraints

• Number of nodes n is between 2 and 100.
• Each element in edges contains a start node x, an end node y, and the edge length w.
  • x, y are integers between 1 and n.
  • w is an integer between -500 and 500.
• Each element in query contains a start node s and an end node e.
  • s, e are integers between 1 and n.

Test Case

Explanation for Test Case 1

• Matches the example in the concept explanation.

Explanation for Test Case 2

• The directed graph's shortest path length array Dist[i][j] (= shortest path length from node i to node j) is as follows: