I'm searching for an algorithm that is similar to dijikstra, but faster. I have to solve the same problem - to find the shortest path to all nodes, starting from a given node. But my teacher tod me, I should find a faster algorithm, as dijikstra could be slow. Also i wanted to ask, if i could use Floyd Marshall's algorithm for that task

CodePudding user response：

Here is a solution to this problem if all arcs are non-negative, otherwise Bellmann-Ford. To get all shortest paths:

1. Do a topological sort.
2. Breadth-first search from the root and update distances. Done.

Just from one node v, start from v, instead of your root. In the worst case your node v is the root anyways. So time-complexity remains = O(|V| |E|).