# Editing Shortest path

**Warning:** You are not logged in. Your IP address will be publicly visible if you make any edits. If you **log in** or **create an account**, your edits will be attributed to your username, along with other benefits.

The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision | Your text | ||

Line 47: | Line 47: | ||

==Single-source shortest paths== | ==Single-source shortest paths== | ||

− | |||

− | |||

− | |||

− | |||

− | |||

==All-pairs shortest paths== | ==All-pairs shortest paths== | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

==Single-pair shortest path== | ==Single-pair shortest path== | ||

We can compute a single-pair shortest path by taking the source <math>s</math> and running single-source shortest paths from it, and simply extracting the shortest path to the destination <math>t</math>. This computes a lot of extra information (namely, the shortest paths to all the other vertices as well), so we might wonder whether it is possible to do better. It turns out that there are no known single-pair shortest path algorithms that outperform single-source shortest paths algorithms ''in the worst case''. Nevertheless, it is often possible to do better in the ''average case''. | We can compute a single-pair shortest path by taking the source <math>s</math> and running single-source shortest paths from it, and simply extracting the shortest path to the destination <math>t</math>. This computes a lot of extra information (namely, the shortest paths to all the other vertices as well), so we might wonder whether it is possible to do better. It turns out that there are no known single-pair shortest path algorithms that outperform single-source shortest paths algorithms ''in the worst case''. Nevertheless, it is often possible to do better in the ''average case''. | ||

− | |||

− | |||

===A* or heuristic search=== | ===A* or heuristic search=== | ||

Line 73: | Line 57: | ||

===Meet-in-the-middle=== | ===Meet-in-the-middle=== | ||

− | Another example of when we don't have to worry much about the worst case, and hence might be able to get a better search time, is when the graph we are searching is extremely large but yet we know that the shortest path is relatively short. For example, consider the Rubik's cube graph, in which each legal position is a vertex and an edge exists between two vertices if the positions they represent can be interconverted with one face turn. There are approximately <math>4.3\times10^ | + | Another example of when we don't have to worry much about the worst case, and hence might be able to get a better search time, is when the graph we are searching is extremely large but yet we know that the shortest path is relatively short. For example, consider the Rubik's cube graph, in which each legal position is a vertex and an edge exists between two vertices if the positions they represent can be interconverted with one face turn. There are approximately <math>4.3\times10^19</math> positions of the Rubik's cube, but the shortest path between any pair of vertices always has length 20 or less.<ref>Tomas Rokicki ''et al.'' "God's Number is 20". Retrieved 2011-03-02 from http://cube20.org/</ref> The graph we are searching may even be infinite. |

− | + | ||

− | + | ||

==References== | ==References== | ||

<references/> | <references/> |