When I run this for node 11 (you get to enter that) it produces a shortest path of 90 via nodes 0,1,4,11. However, there is a shorter path of 85 via nodes 0,2,6,4,11 of length 85.
It appears to be an error in the igraph function, is someone able to confirm or advise otherwise please?
Cheers, Paul
igraph shortest path which is incorrect I think
M = np.array(
[# W 1 2 3 4 5 6 7 8 9 10 11 12 13
[ 0, 20, 35, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #W
[ 20, 0, 0, 0, 50, 35, 0, 0, 0, 0, 0, 0, 0, 0], #1
[ 35, 0, 0, 15, 40, 0, 20, 0, 0, 0, 0, 0, 0, 0], #2
[ 25, 0, 15, 0, 0, 0, 35, 25, 0, 0, 0, 0, 0, 0], #3
[ 0, 50, 40, 0, 0, 20, 10, 0, 20, 0, 0, 20, 0, 0], #4
[ 0, 35, 0, 0, 20, 0, 0, 0, 0, 0, 0, 60, 0, 0], #5
[ 0, 0, 20, 35, 10, 0, 0, 25, 15, 15, 0, 0, 35, 0], #6
[ 0, 0, 0, 25, 0, 0, 25, 0, 0, 20, 0, 0, 0, 0], #7
[ 0, 0, 0, 0, 20, 0, 15, 0, 0, 0, 30, 30, 40, 0], #8
[ 0, 0, 0, 0, 0, 0, 15, 20, 0, 0, 0, 0, 20, 0], #9
[ 0, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 15, 15, 10], #10
[ 0, 0, 0, 0, 20, 60, 0, 0, 30, 0, 15, 0, 0, 20], #11
[ 0, 0, 0, 0, 0, 0, 35, 0, 40, 20, 15, 0, 0, 15], #12
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 20, 15, 0], #13
])
#M[M>0]=1
#weights=[0.6, 0.7, 0.3, 0.6, 0.8, 0.3, 0.7, 0.9, 0.6, 0.3, 0.8, 0.9, 0.4, 0.5, 0.7, 0.3, 0.4, 1.8, 1.5, 1.7, 0.6, 0.5, 1.4, 1.5, 1.6, 1.8, 1.2, 0.7, 1.5, 1.4, 0.6, 0.5, 1.3, 1.5, 1.2, 1.7, 1.2, 0.6, 1.7, 0.3, 1.6, 0.5, 1.2, 0.8, 0.4, 1.3, 1.7, 0.8, 0.8, 0.7, 0.6, 0.3, 0.8, 0.8, 0.4, 0.7, 0.5, 0.6, 0.8, 0.5]
print("input matrix is symmetrical =", np.all((M == np.transpose(M))))
print()
M=np.triu(M)
m=ig.Graph.Weighted_Adjacency(M)
"""for i in range(m.vcount()):
# g.get_shortest_paths() returns a list of edge ID paths
results = m.get_shortest_paths(
0,
to=i,
weights=m.es["weight"],
output="vpath",
#mode=ALL
)
#print(i, sum(m.es[results[0]]["weight"]),m.es[results[0]]["weight"]),
#for n in results[i]:
# print("{}".format(m.vs[i][n]['name']))"""
#for i in range(m.vcount()):
#for i in range(12):
i = int(input('input node number'))
results = m.get_shortest_paths(0,to=i,weights=m.es["weight"],output="epath")
print("Shortest path 'W' and {} is {} ".format( i,m.es[results[0]]["weight"]))
if len(results[0]) > 0:
# Add up the weights across all edges on the shortest path
distance = 0
for e in results[0]:
distance += m.es[e]["weight"]
print("Shortest weighted distance is: ", distance)
else:
print("End node could not be reached!")
#spanning_tree = m.spanning_tree(weights=weights,return_tree=False)
m.es["color"] = "black"
m.es["width"] = 0.5
m.es[results[0]]["color"] = "red"
m.es[results[0]]["width"] = 3
m.es["label_size"]= 10
fig, ax = plt.subplots(1,1,figsize=(16,24))
ig.plot(
m,
bbox=(512,512),
vertex_size=1,
target=ax,
layout=np.multiply([(0,1),(1,2),(1,1),(1,0),(2,2),(2,3),(2,1),(2,0),(3,2),(3,0),(4,2),(4,3),(4,1),(5,2)],4),
edge_curve=0,
vertex_color="lightblue",
vertex_label=range(m.vcount()),
edge_width=m.es["width"],
edge_label=m.es["weight"],
autocurve=False,
)
plt.show()
print("Shortest path {0}".format(distance))
Looking at the image it seems like the graph is directed (you cant move both ways between nodes, only in the direction indicated by the arrow). So 4 and 6 is connected as 4 -> 6 and in your path you use it as 4 <- 6 that is not valid according to the image.
So I would say that igraph is correct and you are wrong.