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

In many applications one wants to obtain the shortest path from a to b.
Depending on the context, the length of the path does not necessarily have to be the length in meter or miles: One can as well look at the cost or duration of a path – therefore looking for the **cheapest path**.

- 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.
- Right-clicking deletes edges and nodes.

A
occured when reading from file:
the contents:

Starting node from where distances and shortest paths are computed. | |

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

BEGIN

d(v[1]) ← 0

FOR j = 2,..,n DO

d(v[j]) ← ∞

FOR i = 1,..,(|V|-1) DO

FOR ALL (u,v) in E DO

d(v) ← min(d(v), d(u)+l(u,v))

FOR ALL (u,v) in E DO

IF d(v) > d(u) + l(u,v) DO

Message: "Negative Circle"

END

i | d(u) | d(v) | l(u,v) |
---|---|---|---|

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

Starting node from where distances and shortest paths are computed. | |

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

BEGIN

d(v[1]) ← 0

FOR j = 2,..,n DO

d(v[j]) ← ∞

FOR i = 1,..,(|V|-1) DO

FOR ALL (u,v) in E DO

d(v) ← min(d(v), d(u)+l(u,v))

FOR ALL (u,v) in E DO

IF d(v) > d(u) + l(u,v) DO

Message: "Negative Circle"

END

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

Starting node from where distances and shortest paths are computed. | |

Edge that has already been selected. | |

Edge that has been selected in the previous step. |

The Bellman-Ford Algorithm can compute all distances correctly in only one phase.

To do so, he has to look at the edges in the **right sequence**.
**This ordering is not easy to find** – calculating it takes the same time as the Bellman-Ford Algorithm itself.

As one can see in the example: The ordering on the left in reasonable, after one phase the algorithm has correctly determined all distances. This is not the case on the right.

In this exercise you can test how many phases the algorithm needs for different sequences of the edges.

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