search

networkx / networkx

Network Analysis in Python
https://networkx.org
Other
14.96k stars 3.25k forks source link

A star not find the same path when switch the start and the end point in an undirected graph #4544

Closed ZhengZhongyuan11 closed 3 years ago

ZhengZhongyuan11 commented 3 years ago

Hi guys,

Recently when I used networkx library to build a undirected graph, and then used astar to search for the shortest path, I found that if I switch the start and the end point, astar_path will return different sequence. I wonder why this happens and can anybody help me?

Thanks!

dschult commented 3 years ago

There can be two paths with the same length. When you try to find the path in the opposite direction, it will not always give the same path (if there are more than one path with the same length).

But you don't need to find the path going the other direction... You can reverse the order of the nodes.

ZhengZhongyuan11 commented 3 years ago

There can be two paths with the same length. When you try to find the path in the opposite direction, it will not always give the same path (if there are more than one path with the same length).

But you don't need to find the path going the other direction... You can reverse the order of the nodes.

Hi dschult,

Thanks for your reply, but I have checked the length, it is not exactly same, the length of reverse order is 24 and the length of in-order sequence is 17. Do you know why this happens?

jarrodmillman commented 3 years ago

Would you mind sharing the example where you see the problem? Thanks!

dschult commented 3 years ago

It sounds like you might have a directed graph. In that case, the direction of the path will impact the shortest path. You can't go the opposite direction along the path.

If not, then I agree with @jarrodmillman . We need more information. Please share a small graph which shows the problem.

ZhengZhongyuan11 commented 3 years ago

Thanks for your reply! I think it is because of my fault, and I have figured it out.