I looked into all pair shortest path routing algorithms to use for traffic simulations. I found that the Floyd–Warshall algorithm works well for my purpose. I use it with the path reconstruction adaption as described in https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
I also needed to find a way to calculate alternative shortest paths when some nodes are "restricted/closed" (e.g. a street segment cannot be used due to construction). I wanted to find shortest paths for those cases solely based on the distance matrix without recalculating the entire OD matrix based on the adapted network geometry. I could not find any literature and therefore developed my own algorithm that allows me to calculate shortest paths based on the original matrix even if some nodes are removed.
I consider to publish it, but before going through the hassle of writing I wanted to know if I may have failed to find literature describing something similar as I did.
To put it short: Is there an all pairs shortest path algorithm that allows obstacle avoidance using the OD matrix that was computed without the restrictions?
best regards, Christoph
أكثر...
I also needed to find a way to calculate alternative shortest paths when some nodes are "restricted/closed" (e.g. a street segment cannot be used due to construction). I wanted to find shortest paths for those cases solely based on the distance matrix without recalculating the entire OD matrix based on the adapted network geometry. I could not find any literature and therefore developed my own algorithm that allows me to calculate shortest paths based on the original matrix even if some nodes are removed.
I consider to publish it, but before going through the hassle of writing I wanted to know if I may have failed to find literature describing something similar as I did.
To put it short: Is there an all pairs shortest path algorithm that allows obstacle avoidance using the OD matrix that was computed without the restrictions?
best regards, Christoph
أكثر...