CODEWITHSUNDEEP
algorithmgraphpath-finding
Lachezar Valev
Lachezar Valev

Reputation: 15

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

Upvotes: 0

Views: 1085

Answers (2)

Carlos Julio
Carlos Julio

Reputation: 410

Dijkstra is the optimal algorithm to find the shortest path from a node to the rest if it´s not a specific graph always as arc weigth is positive otherwise you need use Bellmann-Ford algorithm. In your case it´s a DAG, this is a special graph, how it has not cycles, you never come back to a previous state, so, there is a unique path from any node to another(or none). Thus, algorithms as BFS or DFS are suitable even if the arcs are negative.

Upvotes: 0

Luka
Luka

Reputation: 156

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

Upvotes: 2

Related Questions