Image foresting transform: Difference between revisions

Revision as of 16:11, 1 June 2022

Revision as of 16:03, 2 June 2022

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, “[http://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf 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, “[https://web.archive.org/web/20220602081239/https://apps.dtic.mil/dtic/tr/fulltext/u2/606258.pdf On a Routing Problem]{{dead link|date=May 2022|bot=medic}}{{cbignore|bot=medic}},” Quarterly of Applied Math., vol. 16, pp. 87-90, 1958</ref> that computed the cost of the paths in a general graph. The [[Bucket sort]]ing technique is how Dial improved on the algorithm a decade later.<ref name="Falcao"/><ref name="Dial">R.B. Dial, “[https://www.sciencedirect.com/science/article/pii/0191261580900144 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"/>==