To find the shortest all possible paths in a network what algorithm is used?

Question

dharani m 2015-12-16

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/260639-to-find-the-shortest-all-possible-paths-in-a-network-what-algorithm-is-used

评论： Christine Tobler 2015-12-17

It must displays the all possible paths from a source node to destination node.Because i am using genetic algorithm for selecting the optimal path.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Christine Tobler 2015-12-17

How do you define the optimal path? MATLAB's graph object currently only returns the shortest path between source and destination nodes, not all paths. This is mainly because the number of paths between two nodes can grow exponentially with the number of nodes in a graph.

Also, there are different ways of defining "all paths". For example: Would you count a path that passes through the same node twice? What about a path that passes through the same edge twice?

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Image Analyst 2015-12-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/260639-to-find-the-shortest-all-possible-paths-in-a-network-what-algorithm-is-used#answer_203491

Why bother finding all possible paths? Just find the best one - it's not required to find all of them before you find the best one. Anyway, my favorite is A* but there are a bunch of alternatives, some of which excel in certain situations, and are also listed on the page for A*: https://en.wikipedia.org/wiki/A*_search_algorithm

You might also look how it's done with images: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/