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 9: | Line 9: | ||
'''Corollary''': Assuming our graphs have no cycles of negative weight, the restriction that the shortest paths be simple is immaterial. Therefore, we will assume in the foregoing discussion that our graphs have no cycles of negative weight, for the problem of finding shortest ''simple'' paths in graphs containing negative-weight cycles is NP-complete. | '''Corollary''': Assuming our graphs have no cycles of negative weight, the restriction that the shortest paths be simple is immaterial. Therefore, we will assume in the foregoing discussion that our graphs have no cycles of negative weight, for the problem of finding shortest ''simple'' paths in graphs containing negative-weight cycles is NP-complete. | ||
− | '''Corollary''': In a finite | + | '''Corollary''': In a finite graph, a shortest path always exists. (To prove this we simply use the fact that the graph has a finite number of simple paths, and only simple paths need be considered. So one of them must be the shortest.) |
==Variations== | ==Variations== |