The Bellman-Ford algorithm computes single-source shortest paths in a weighted
digraph (where some of the edge weights may be negative). Dijkstra's algorithm
accomplishes the same problem with a lower running time, but requires edge
weights to be non-negative. Thus, Bellman-Ford is usually used only when there
are negative edge weights.
Bellman Ford runs in O(VE) time, where V and E are the number of vertices and
edges.
The correctness of the algorithm can be shown by induction. The precise
statement shown by induction is:
Lemma. After i repetitions of for cycle:
* If Distance(u) is not infinity, it is equal to the length of some path
from s to u;
* If there is a path from s to u with at most i edges, then Distance(u) is
at most the length of the shortest path from s to u with at most i edges.
Proof. For the base case of induction, consider i=0 and the moment before for
cycle is executed for the first time. Then, for the source vertex,
source.distance = 0, which is correct. For other vertices u, u.distance =
infinity, which is also correct because there is no path from source to u with
0 edges.
For the inductive case, we first prove the first part. Consider a moment when
a vertex's distance is updated by v.distance := u.distance + uv.weight. By
inductive assumption, u.distance is the length of some path from source to u.
Then u.distance + uv.weight is the length of the path from source to v that
follows the path from source to u and then goes to v.
For the second part, consider the shortest path from source to u with at most
i edges. Let v be the last vertex before u on this path. Then, the part of the
path from source to v is the shortest path between source to v with i-1 edges.
By inductive assumption, v.distance after i-1 cycles is at most the length of
this path. Therefore, uv.weight + v.distance is at most the length of the path
from s to u. In the ith cycle, u.distance gets compared with uv.weight +
v.distance, and is set equal to it if uv.weight + v.distance was smaller.
Therefore, after i cycles, u.distance is at most the length of the shortest
path from source to u that uses at most i edges.
When i equals the number of vertices in the graph, each path will be the
shortest path overall, unless there are negative-weight cycles. If a
negative-weight cycle exists and is accessible from the source, then given any
path, a shorter one exists, so there is no shortest path. Otherwise, the
shortest path will not include any cycles (because going around a cycle would
not make the path shorter), so each shortest path visits each vertex at most
once, and its number of edges is less than the number of vertices in the
graph. Therefore, each path stored in the graph by this point is the shortest
path.
End of proof.
--------------------------
Dijkstra's algorithm, named after its discoverer, Dutch computer scientist
Edsger Dijkstra, is an algorithm that solves the single-source shortest path
problem for a directed graph with nonnegative edge weights.
For example, if the vertices of the graph represent cities and edge weights
represent driving distances between pairs of cities connected by a direct
road, Dijkstra's algorithm can be used to find the shortest route between two
cities.
The input of the algorithm consists of a weighted directed graph G and a
source vertex s in G. We will denote V the set of all vertices in the graph G.
Each edge of the graph is an ordered pair of vertices (u,v) representing a
connection from vertex u to vertex v. The set of all edges is denoted E.
Weights of edges are given by a weight function w: E --> [0,infinity];
therefore w(u,v) is the non-negative cost of moving from vertex
u to vertex v. The cost of an edge can be thought of as (a generalization of)
the distance between those two vertices. The cost of a path between two
vertices is the sum of costs of the edges in that path. For a given pair of
vertices s and t in V, the algorithm finds the path from s to t with lowest
cost (i.e. the shortest path). It can also be used for finding costs of
shortest paths from a single vertex s to all other vertices in the graph.
The algorithm works by keeping for each vertex v the cost d[v] of the shortest
path found so far between s and v. Initially, this value is 0 for the source
vertex s (d[s]=0), and infinity for all other vertices, representing the fact
that we do not know any path leading to those vertices (d[v]=infinity for
every v in V, except s). When the algorithm finishes, d[v] will be the cost of
the shortest path from s to v -- or infinity, if no such path exists.
The basic operation of Dijkstra's algorithm is edge relaxation: if there is an
edge from u to v, then the shortest known path from s to u (d[u]) can be
extended to a path from s to v by adding edge (u,v) at the end. This path will
have length d[u]+w(u,v). If this is less than the current d[v], we can replace
the current value of d[v] with the new value. Edge relaxation is applied until
all values d[v] represent the cost of the shortest path from s to v. The
algorithm is organized so that each edge (u,v) is relaxed only once, when d[u]
has reached its final value.
The notion of "relaxation" comes from an analogy between the estimate of the
shortest path and the length of a helical tension spring, which is not
designed for compression. Initially, the cost of the shortest path is an
overestimate, likened to a stretched out spring. As shorter paths are found,
the estimated cost is lowered, and the spring is relaxed. Eventually, the
shortest path, if one exists, is found and the spring has been relaxed to its
resting length.
The algorithm maintains two sets of vertices S and Q. Set S contains all
vertices for which we know that the value d[v] is already the cost of the
shortest path and set Q contains all other vertices. Set S starts empty, and
in each step one vertex is moved from Q to S. This vertex is chosen as the
vertex with lowest value of d[u]. When a vertex u is moved to S, the algorithm
relaxes every outgoing edge (u,v).
The simplest implementation of the Dijkstra's algorithm stores vertices of set
Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply
a linear search through all vertices in Q. In this case, the running time is
O(V^2).
For sparse graphs, that is, graphs with much less than V^2 edges, Dijkstra's
algorithm can be implemented more efficiently by storing the graph in the form
of adjacency lists and using a binary heap or Fibonacci heap as a priority
queue to implement the Extract-Min function. With a binary heap, the algorithm
requires O((E+V)lgV) time, and the Fibonacci heap improves this to O(E + VlgV).
--------------------------
Johnson's algorithm is a way to solve the all-pairs shortest path problem in a
sparse, weighted, directed graph.
First, it adds a new node with zero weight edge from it to all other nodes,
and runs the Bellman-Ford algorithm to check for negative weight cycles and
find h(v), the least weight of a path from the new node to node v. Next it
reweights the edges using the nodes' h(v) values. Finally for each node, it
runs Dijkstra's algorithm and stores the computed least weight to other nodes,
reweighted using the nodes' h(v) values, as the final weight. The time
complexity is O(V^2log V + VE).
--------------------------
The Floyd-Warshall algorithm takes as input an adjacency matrix
representation of a weighted, directed graph (V, E). The weight of a path
between two vertices is the sum of the weights of the edges along that path.
The edges E of the graph may have negative weights, but the graph must not
have any negative weight cycles. The algorithm computes, for each pair of
vertices, the minimum weight among all paths between the two vertices. The
running time complexity is O(|V|^3).
The algorithm is based on the following observation: Assuming the vertices of
a directed graph G are V = {1, 2, 3, 4, ..., n}, consider a subset {1, 2, 3,
..., k}. For any pair of vertices i, j in V, consider all paths from i to j
whose intermediate vertices are all taken from {1, 2, ..., k}, and p is a
minimum weight path from among them. The algorithm exploits a relationship
between path p and shortest paths from i to j with all intermediate vertices
in the set {1, 2, ..., k-1}. The relationship depends on whether or
not k is an intermediate vertex of path p.