Dijkstra–Scholten algorithm: Difference between revisions

Revision as of 01:17, 17 December 2009

Revision as of 09:09, 24 May 2010

Line 19:

==Dijkstra-Scholten algorithm for directed acyclic graphs==

* The algorithm for a tree can be extended to acyclic directed graphs. We add an additional edgeinteger attribute [[Deficit]] to each edge.

* On an incoming edge, Deficit will denote the difference between the number of messages received and the number of signals sent in reply.

* When a node wishes to terminate, it waits until it has received signals from outgoing edges reducing their deficits to zero.