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.
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.
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.
Dijkstra's Algorithm
Dijkstra’s Algorithm computes the shortest path between any two nodes whenever all adge weights are non-negative.
Floyd-Warshall Algorithm
The Floyd-Warshall Algorithm computes shortest paths between all pairs of nodes. It also works with negative edge weights.
