Logo Shortest paths in Graphs:
                                                    The A* algorithm Technische Universität München
Simple Graph with 4 nodes.

What's the cheapest way from left to right?

An informed search for the shortest path

You want to know, how to get from Munich to Frankfurt as fast as possible? Dijkstra's Algorithm can help you! But if you already know that Munich lies shouth of Frankfurt, this algorithm may be unnecessarily slow. Dijkstra's algorithm expands its search uniformly into all directions. It is, however, much faster to simply ignore most cities north of Frankfurt.

The A* algorithm was designed for these kinds of problems. It is similar to Dijkstra's algorithm, but its approach is much more goal-oriented. For the target node, Munich, it first computes an estimate of the shortest distance. Based on this estimate, it will achieve a fast computation

The A* algorithm can also compute the shortest distances between one city and all other cities. And the edges can describe costs, distances, or some other measure that is helpful for the user. It requires, however, that all edge costs (which is how we call the edge labels) must not be negative.

This applet presents the A* algorithm, which calculates the shortest path between two nodes in graphs with positive edge costs.

What do you want to do first?

SVG Download

Legend

Knoten Node
Knoten Edge with weight 50

Legend

Which graph do you want to execute the algorithm on?

Start with an example graph:

Modify it to your desire:

  • To create a node, make a double-click in the drawing area.
  • To create an edge, first click on the output node and then click on the destination node.
  • The edge weight is changed with a double-click on the edge.
  • Right-clicking deletes edges and nodes.

Download the modified graph:

Download

Upload an existing graph:

A

occured when reading from file:

the contents:

                    

What next?

SVG Download

Legend

Starting node Starting node from where the shortest path to the target is computed.
Target node Target node, towards whom the shortest path is computed.
Finished node Node that has already been processed
Current node Node being processed.
Node in priority queue Node in the priority queue.
Predecessor edge "Predecessor edge" that is used by the shortest path to the node.

Legend

Algorithm status

BEGIN

d(v[1]) ← 0, parent(v[1]) ← v[1]

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

h(v[i]) ← √(Σ(v[i].coord-ziel.coord)2)

WHILE queue ≠ ∅ DO

u = queue.extractMin()

IF u == ziel DO RETURN "Path found!"

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, f = dist + h(u)

parent(w) = u

ELSE IF parent(w) == NULL THEN

d(w) = dist, f = dist + h(u)

parent(w) = u, queue.insert(w,f)

RETURN "Target unreachable"

END

Priority Queue:

Your browser does not support HTML5 Canvas. Please use a modern browser, i.e.Mozilla Firefox

Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.

SVG Download

Legend

Starting node Starting node from where the shortest path to the target is computed.
Target node Target node, towards whom the shortest path is computed.
Finished node Node that has already been processed
Current node Node being processed.
Node in priority queue Node in the priority queue.
Predecessor edge "Predecessor edge" that is used by the shortest path to the node.

Legend

Exercise: How does Dijkstra's algorithm work on a grid?

BEGIN

d(v[1]) ← 0

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

WHILE queue ≠ ∅ DO

u = queue.extractMin()

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, parent(w) = (u,w)

ELSE IF parent(w) == NULL THEN

d(w) = dist, parent(w) = (u,w)

queue.insert(w,dist)

END

Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.

SVG Download

Legend

Starting node Starting node from where the shortest path to the target is computed.
Target node Target node, towards whom the shortest path is computed.
Finished node Node that has already been processed
Current node Node being processed.
Node in priority queue Node in the priority queue.
Predecessor edge "Predecessor edge" that is used by the shortest path to the node.

Legend

Exercise: How does the A* algorithm work on a grid?

BEGIN

d(v[1]) ← 0, parent(v[1]) ← v[1]

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

h(v[i]) ← √(Σ(v[i].coord-ziel.coord)2)

WHILE queue ≠ ∅ DO

u = queue.extractMin()

IF u == ziel DO RETURN "Path found"

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, f = dist + h(u)

parent(w) = u

ELSE IF parent(w) == NULL THEN

d(w) = dist, f = dist + h(u)

parent(w) = u, queue.insert(w,f)

RETURN "Target not reachable"

END

Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.