algorithmgraphpath-finding

Faster Algorithm than Dijikstra for finding shortest path to all nodes starting from one node

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

Solution

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