Hello, I’m getting an unexpected result while trying to find the shortest path in a weighted graph. I am using the python igraph library version 0.10.4 and the first result of get_k_shortest_paths is returning a path using an edge that has a higher weight. Is this expected? If so, does igraph provide a means to get find the minimal weight path?
Code for reproducing the behavior:
import igraph
import matplotlib.pyplot as plt
def pretty_print_weighted_graph(graph: igraph.Graph):
print("Vertices:")
for vertex in graph.vs:
print(f"{vertex.index}: {vertex['name']}")
print("\nEdges:")
for edge in graph.es:
source = graph.vs[edge.source]['name']
target = graph.vs[edge.target]['name']
weight = edge['weight']
print(f"{source} --({weight})--> {target}")
def main():
graph = igraph.Graph(directed=True)
graph.add_vertices(2)
graph.add_edges([(0, 1),
(0, 1)])
weights = [1, 10]
graph.es["weight"] = weights
graph.vs["name"] = [0, 1]
pretty_print_weighted_graph(graph)
# attempt to find the shortest weighted path
start = 0
finish = 1
print("igraph version: ", igraph.__version__)
print("is_weighted? ", graph.is_weighted())
#path = graph.get_shortest_path(v=start, to=finish, mode=igraph.OUT, weights=graph.es["weight"], output="vpath")
path = graph.get_k_shortest_paths(v=start,
to=finish,
k=1,
mode=igraph.OUT,
weights=graph.es["weight"],
output="vpath")[0]
for i in range(1, len(path)):
eid = graph.get_eid(path[i-1], path[i])
print(f"vertex: {graph.vs[path[i]]['name']}")
print(f"eid: {eid}")
print(f"weight: {graph.es[eid]['weight']}")
_, ax = plt.subplots()
igraph.plot(graph, target=ax)
plt.show()
if __name__ == "__main__":
main()
