Incorrect shortest path in Python igraph?

Question

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))

Answer 1

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.

Answer 2

Just use mode="all" in the function

results = m.get_shortest_paths(0, to=i, weights=m.es["weight"], output="epath", mode="all")

mode can be out (the default), in or all. So in case of directed graphs you can go just in the directions of the arrows if you use the default out value, so 6->4 step is not allowed. With all you can go both directions, so you get the path you want:

The documentation can be found here

Answer 3

Thank you for the comments.

I had been making the matrix into upper diagonal form. After removing this command I now get the correct answer.

So yes, igraph is correct, doing exactly what it should and I was wrong. I guess that is how we learn.