Image foresting transform: Difference between revisions

Revision as of 12:11, 17 May 2018

Revision as of 12:20, 17 May 2018

Line 5:

==History <ref name="Falcao"/>==

In 1959 Dijkstra used a [[Heap (data structure)|balanced heap data structure]]<ref name="Falcao"/><ref name="Dij">E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, pp. 269-271, 1959</ref> to improve upon an algorithm presented by Moore in 1957<ref name="Falcao"/><ref name="Moo">E.F. Moore, “The Shortest Path through a Maze,” Proc. Int’l Symp. Theory of Switching, pp. 285-292, Apr. 1959</ref> and Bellman in 1958<ref name="Falcao"/><ref name="Bell">R. Bellman, “On a Routing Problem,” Quarterly of Applied Math., vol. 16, pp. 87-90, 1958</ref> that computed the cost of the paths in a general graph. The [[Bucket sortingsort]]ing technique is how Dial improved on the algorithm a decade later.<ref name="Falcao"/><ref name="Dial">R.B. Dial, “Shortest-Path Forest with Topological Ordering,” Comm. ACM, vol. 12, no. 11, pp. 632-633, Nov. 1969</ref> The algorithm has been tweaked and modified in many ways since then. It is on this version that Falcao, Stolfi, and Lotufo improved upon.<ref name="Falcao"/>

==Definition <ref name="Falcao"/>==