Difference between revisions of "TADM2E 6.21"
From Algorithm Wiki
(Redirected page to UNTV) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | Step 1: | |
| + | |||
| + | Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m) | ||
| + | |||
| + | Step 2: | ||
| + | |||
| + | Go through vertices in topological order. Initially all vertices marked as inaccessible and only starting vertex marked with 0 distance. | ||
| + | For every vertex in cycle, if it is accessible, we update all its children with new distance if new distance is shorter then previous one. | ||
| + | Topological sorting ensures that we don't ever need to go backtrack. This is O(n + m). | ||
| + | |||
| + | Total running bound is O(n+m), which is linear as requested. | ||
Latest revision as of 00:43, 1 August 2020
Step 1:
Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m)
Step 2:
Go through vertices in topological order. Initially all vertices marked as inaccessible and only starting vertex marked with 0 distance. For every vertex in cycle, if it is accessible, we update all its children with new distance if new distance is shorter then previous one. Topological sorting ensures that we don't ever need to go backtrack. This is O(n + m).
Total running bound is O(n+m), which is linear as requested.
