Re: [igraph] Generating Dijkstra Shortest Path

[Tamas Nepusz]

> G.shortest_paths_dijkstra(vertice1, vertice2) where vertice1 and vertice2
> represent the source and target, of course. I would like for this to return
> a list of vertex names of the shortest path using the weights/costs that
> I passed when I added the edges. Am I doing this correct?
Please read the documentation of shortest_paths_dijkstra():

http://igraph.org/python/doc/igraph.Graph-class.html#shortest_paths_dijkstra

You can see that the function has a "weights" argument with a default value of
None. The documentation of the "weights" argument says:

"a list containing the edge weights. It can also be an attribute name (edge
weights are retrieved from the given attribute) or None (all edges have equal
weight)."

So, by default, shortest_paths_dijkstra() will not consider edge weights. You
have to pass at least the name of the edge attribute containing weights
("weight" in your case):

G.shortest_paths_dijkstra(vertex1, vertex2, weights="weight")

> I would like to print the shortest path of the vertex names I added
> previously. I hope this is understandable.
Use get_shortest_paths() with the "weights" argument -- this will run
Dijkstra's algorithm but return the indices of the vertices in the shortest
paths instead:

http://igraph.org/python/doc/igraph.GraphBase-class.html#get_shortest_paths

paths = G.get_shortest_paths(vertex1, vertex2, weights="weight")

The result will be a list with one element: the path from vertex1 to vertex2.
Since the path contains vertex IDs by default, you need to map them to names:

path = paths[0]
path_with_names = G.vs[path]["name"]

T.