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