incorrect shortest paths solutions when impendance values are particularly small or large

[bonza2]

Description of the bug

I am encountering incorrect shortest path solutions when using the Network.shortest_path (and Network.shortest_paths) method on a network with impedance values of small or large (though still reasonable) orders of magnitude. I have included a very simple toy example below that captures the problem. Essentially, when the impedance values are scaled to a sufficiently small order of magnitude (by experiment seems to be ~1e-4) or large order of magnitude (by experiment seems to be ~1e7), the shortest path solution is no longer correct (and, incidentally, appears to revert to a solution that traverses the least number of nodes, rather than minimizing total impedance, though my example doesn't explore this aspect of the problem).

Environment

• Operating system: Windows 10 Enterprise

• Python version: 3.9.10

• Pandana version: 0.6.1

Paste the code that reproduces the issue here:

import numpy as np
import pandana as pdna
import pandas as pd


nodes = [1, 2, 3, 4, 5]
nodes = pd.DataFrame(
    np.random.uniform(size=(5, 2)), columns=["x", "y"], index=nodes
)

edges = pd.DataFrame(
    [
        [1, 2, 0.001],
        [2, 3, 0.001],
        [3, 4, 0.001],
        [1, 5, 0.002],
        [5, 4, 0.002],
    ],
    columns=["from_node", "to_node", "weight"]
)

net = pdna.Network(nodes["x"], nodes["y"], edges["from_node"], edges["to_node"], edges[["weight"]], twoway=False)

net.shortest_path(1, 4)

>>> array([1, 2, 3, 4], dtype=int64)

The above example produces the expected solution.

Now, use exactly the same nodes and edges, but scale the impedance values down by a factor of 10:

net = pdna.Network(nodes["x"], nodes["y"], edges["from_node"], edges["to_node"], edges[["weight"]]  / 10, twoway=False)

net.shortest_path(1, 4)

>>> array([1, 5, 4], dtype=int64)

In the second example, clearly the more expensive and incorrect route has been chosen. The same behavior is observed at the larger end of impedance values also: for example, using the above example, when the impedance values are 1e7 instead .0001, and 2e7 instead of .0002, the same behavior occurs. I'm at a loss as to why this is happening?

Thank you for your help!

[stefancoe]

I am experiencing the same issue. The returned distance between two nodes of interest is about a mile shorter than the Euclidian distance. NetworkX is able to return a distance greater than the Euclidean distance using the same network. Happy to post code and data if that helps.

[jwrap]

Has there been any headway on this, or do we know why the calculations are coming out this way? I think I am having a similar issue, where the shortest_path_length returned is less than the sum of impedances on the sequence of edges returned by shortest_path.

I just tested the outputs by changing the unit of my impedance from minutes to seconds (there were some impedances going down to about 0.002 minutes) and it looks to be more accurate / aligned with the sum of impedances from the shortest_path output. So I guess that's an ad-hoc solution.