Dijkstra's algorithm: Difference between revisions

Revision as of 22:27, 14 April 2003

Revision as of 22:29, 14 April 2003

Line 55:

OSPF [[Open shortest path first]] is a well known real world implemenationimplementation used in internet routing.

A related problem is the [[traveling salesman problem]], which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. That problem is [[NP-hard]], so it can't be solved by Dijkstra's algorithm, nor by any other known, polynomial-time algorithm.