floyd_warshall function does not correctly handle multiple edges between the same nodes #668
Description
Introduction
The floyd_warshall function in the petgraph crate does not correctly handle graphs where multiple edges exist between the same pair of nodes (i.e., multigraphs). When multiple edges are present between two nodes, the function overwrites the distance between those nodes with the cost of the last edge processed, rather than considering the minimum cost among all edges.
Steps To Reproduce
Running the following code demonstrates the issue:
use petgraph::Graph;
use petgraph::algo::floyd_warshall;
use petgraph::Undirected;
fn main() {
let mut graph = Graph::<(), i32, Undirected>::new_undirected();
let node_a = graph.add_node(());
let node_b = graph.add_node(());
// Add multiple edges between the same nodes with different weights
graph.add_edge(node_a, node_b, 15); // This edge will be ignored
graph.add_edge(node_a, node_b, 25); // This edge is longer than the previous one but used in the result
let result = floyd_warshall(&graph, |edge| *edge.weight()).unwrap();
for edge in graph.edge_indices() {
let (a, b) = graph.edge_endpoints(edge).unwrap();
println!("Edge from {:?} to {:?} with weight {:?}", a, b, graph[edge]);
}
println!("Distance from A to B: {:?}", result.get(&(node_a, node_b)));
}Actual Results
Edge from NodeIndex(0) to NodeIndex(1) with weight 15
Edge from NodeIndex(0) to NodeIndex(1) with weight 25
Distance from A to B: Some(25)
but I expect Some(15).
Cause Analysis
In the implementation of floyd_warshall, when initializing the distance matrix, the function overwrites the distance between two nodes without checking if the new edge provides a shorter path. Specifically, in the following code segment:
// Initialize distances for paths with no intermediate nodes
for edge in graph.edge_references() {
dist[graph.to_index(edge.source())][graph.to_index(edge.target())] = edge_cost(edge);
if !graph.is_directed() {
dist[graph.to_index(edge.target())][graph.to_index(edge.source())] = edge_cost(edge);
}
}This code assigns the edge cost directly to the distance matrix dist without comparing it to any existing value. As a result, if multiple edges exist between the same nodes, the last edge's weight overwrites any previous values, regardless of whether it's the minimum.
Proposed Solution
Modify the initialization step to consider the minimum edge weight between two nodes. Here's the corrected code:
// Initialize distances for paths with no intermediate nodes
for edge in graph.edge_references() {
let i = graph.to_index(edge.source());
let j = graph.to_index(edge.target());
let cost = edge_cost(edge);
if dist[i][j] > cost {
dist[i][j] = cost;
if !graph.is_directed() {
dist[j][i] = cost;
}
}
}Summary
The floyd_warshall function in the petgraph crate incorrectly handles multiple edges between the same nodes by overwriting the existing distance with each edge's weight without considering if it's smaller. This results in inaccurate shortest path computations in graphs where multiple edges exist between node pairs.