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