Shortest Paths

One of the most common applications of graphs in everyday life is the representation of infrastructure and communication networks. A street map, bus lines in a city or the flights offered by an airline; they can all be represented by a graph.

The search for a paths between given nodes in these graphs is of great importance. Of special interest are ‘cost efficient’ paths, where ‘cost efficient’ can have diverse interpretations: Maybe it is the shortest or fastest way, the one that can be traversed with minimum fuel consumption, paying a minimum fare or one that avoids speed traps.

logo for the category 'A* Algorithm'
A* Algorithm

The A* (pronounced ‘A Star’) Algorithm works similarly to Dijkstra’s Algorithm. However, it uses an additional heuristic for the distance between nodes and thus is normally faster.

logo for the category 'Bellman-Ford Algorithm'
Bellman-Ford Algorithm

In contrast to Dijkstra’s algorithm and the A* algorithm, the Bellman-Ford Algorithm also return shortest paths when negative edge weights are present.

logo for the category 'Dijkstra's Algorithm'
Dijkstra's Algorithm

Dijkstra’s Algorithm computes the shortest path between any two nodes whenever all adge weights are non-negative.

logo for the category 'Floyd-Warshall Algorithm'
Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm computes shortest paths between all pairs of nodes. It also works with negative edge weights.