Dijkstra’s Algorithm

Allgemein

• Best-First-Search
• Sehr große Graphen – z.B. Routenplaner
• Bei negative Kantengewichte nicht korrekt! → Bellmann-Ford Algorithmus

Definition

Laufzeit

Notizen aus RDL

• However, unlike A*, its cost function has only one term, namely the exact cost g(q). This is the actual cost of moving from the start node to node q.
• If the actual cost of moving from a node to an adjacent node is the identical for all nodes in the graph, then Dijkstra’s algorithm is identical to Breadth-First Search.

⇒ ROS 2 Navigation Stack includes Dijkstra’s and A* path planners.