i confused why topological sorting shortest path big-o of o(v+e). here algorithm:
1. topologically sort g l; 2. set distance source 0; 3. set distances other vertices infinity; 4. each vertex u in l 5. - walk through neighbors v of u; 6. - if dist(v) > dist(u) + w(u, v) 7. - set dist(v) <- dist(u) + w(u, v);
seem me it's o(v*e) rather o(v+e) because has 2 nested loops. according wikipedia it's o(v+e), missing here ? https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
remember edges directed, same edge never considered more 1 vertex. despite nested loop, end looking @ each vertex , each edge once.
Comments
Post a Comment