unexpected shortest_path result

Hello --
I am getting an unexpected shortest path (with weighted costs) result. I
have isolated it to a simple script to illustrate; the files are at

- graph: graph_after_1iter_157_277.xml.gz
- python script to illustrate my issue: path_debug.py
- log file output of python script: path_debug.log
The workbook, path_debug.xls, is just an excel version of path_debug.log
with a calculated column (in orange) inserted to show what I expect to be
the shortest distance to the given vertex.

The script path_debug.py:
1) finds the shortest path from a source to a target and prints the details
2) prints the details of what I expect to be the shortest path

I cannot figure out why the second path has the cost that it's printing...
Mostly it's as expected, but the yellow highlighted cells are what baffles

The graph is a pseudo-dual network so it's a bit confusing; the vertices
symbolize links in a street network and the edges symbolize a turn from the
incoming link to the outgoing link.

Any help would be greatly appreciated!

You might be hitting the following bug which was fixed a while ago:


This fix has not yet made into a release, so you should try the git
version. Alternatively, you may get the distances from the
shortest_distance function without the 'target' option, and compare.


Hi Lisa,

I recently posted Issue #188:
https://git.skewed.de/count0/graph-tool/issues/188 which Tiago resolved in
the current master branch.

Can you run the simple example I posted? I see in your path_debug.py that
you use shortest_distance with a specified target which in version 2.2.35
stops the search as soon as the target node is discovered during Dijkstra's

If this is the problem then you either need to compile the current (git)
version of graph-tool or to wait for the next pre-compiled packages.

Hope that helps,

Aha that does sound promising! I'll try pulling the current git version
and see if it fixes it.
Thank you both!

attachment.html (3.15 KB)

The current git version of the code fixed my problem. Thank you!

attachment.html (3.84 KB)

One more question --

Do you know when you'll be releasing a version with this fix? I'm
wondering if I should build an amazon image with the current code or if I
should wait, so a time estimate would be useful.

Thank you!

attachment.html (364 Bytes)

I can't give you an expectation date. This will be done as time permits.
It will happen hopefully during the next week or two.