Graph Theory37 sections · 1633 units
Open in Course

CSES 1672 Shortest Routes II - Handling Multiple Edges

(Taking the minimum weight)

If the graph has multiple edges between the same pair of vertices, take the one with minimum weight. When reading edges, if there is already an edge from ii to jj with weight w1w_1, and you read a new edge with weight w2w_2, set dist[i][j] = min(w_1, w_2).

This ensures the distance matrix starts with the best direct edges before Floyd-Warshall runs. Forgetting this can give wrong answers if the input has duplicate edges.