|
|
| 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.
| |
