- Introduction
- Create a graph
- Run the algorithm
- Description of the algorithm
- Exercise 1
- Exercise 2
- More

What's the cheapest way from left to right?

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.

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

A
occured when reading from file:
the contents:

Starting node from where the shortest path to the target is computed. | |

Target node, towards whom the shortest path is computed. | |

Node that has already been processed | |

Node being processed. | |

Node in the priority queue. | |

"Predecessor edge" that is used by the shortest path to the node. |

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

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

Starting node from where the shortest path to the target is computed. | |

Target node, towards whom the shortest path is computed. | |

Node that has already been processed | |

Node being processed. | |

Node in the priority queue. | |

"Predecessor edge" that is used by the shortest path to the node. |

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

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

Starting node from where the shortest path to the target is computed. | |

Target node, towards whom the shortest path is computed. | |

Node that has already been processed | |

Node being processed. | |

Node in the priority queue. | |

"Predecessor edge" that is used by the shortest path to the node. |

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

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