WARSHALL ALGORITHM

INTRODUCTION
In computer science, the Floyd–Warshall algorithm (also known
as Floyd's algorithm, Roy–Warshall algorithm, Roy–Floyd
algorithm, or the WFI algorithm[clarification needed]) is
a graphanalysis algorithm for finding shortest paths in a weighted
graph (with positive or negative edge weights). A single execution of the
algorithm will find the lengths (summed weights) of the shortest paths
between all pairs of vertices though it does not return details of the paths
themselves. The algorithm is an example of dynamic programming. It
was published in its currently recognized form by Robert Floyd in 1962.
However, it is essentially the same as algorithms previously published
by Bernard Roy in 1959 and also by Stephen Warshall in 1962 for
finding the transitive closure of a graph.
 ALGORITHM
The Floyd–Warshall algorithm compares all possible paths through the
graph between each pair of vertices. It is able to do this with only Θ(|V|3)
comparisons in a graph. This is remarkable considering that there may
be up to Ω(|V|2) edges in the graph, and every combination of edges is
tested. It does so by incrementally improving an estimate on the shortest
path between two vertices, until the estimate is optimal.
Consider a graph G with vertices V, each numbered 1 through N. Further
consider a function shortestPath(i, j, k) that returns the shortest possible
path from i to j using vertices only from the set {1,2,...,k} as
intermediate points along the way. Now, given this function, our goal is
to find the shortest path from each i to each j using only vertices 1
to k + 1.
There are two candidates for each of these paths: either the true shortest
path only uses vertices in the set {1, ..., k}; or there exists some path that
goes from i to k + 1, then from k + 1 to j that is better. We know that the
best path from i to j that only uses vertices 1 through k is defined by
shortestPath(i, j, k), and it is clear that if there were a better path
from i to k + 1 to j, then the length of this path would be the
concatenation of the shortest path from i to k + 1 (using vertices in
{1, ..., k}) and the shortest path from k + 1 to j (also using vertices
in {1, ..., k}).
Therefore, we can define shortestPath(i, j, k) in terms of the
following recursive formula:

This formula is the heart of the Floyd–Warshall algorithm. The

algorithm works by first computing shortestPath(i, j, k) for all (i, j)
pairs for k = 1, then k = 2, etc. This process continues until k = n, and
we have found the shortest path for all (i, j) pairs using any
intermediate vertices
 BEHAVIOUR WITH NEGATIVE CYCLES

For numerically meaningful output, the Floyd–Warshall algorithm

assumes that there are no negative cycles (in fact, between any pair of
vertices which form part of a negative cycle, the shortest path is not
well-defined because the path can be arbitrarily negative). Nevertheless,
if there are negative cycles, the Floyd–Warshall algorithm can be used to
detect them. The intuition is as follows:

 The Floyd–Warshall algorithm iteratively revises path lengths

between all pairs of verticies (i, j), including where i = j;
 Initially, the length of the path (i,i) is zero;
 A path {(i,k), (k,i)} can only improve upon this if it has length less
than zero, i.e. denotes a negative cycle;
 Thus, after the algorithm, (i,i) will be negative if there exists a
negative-length path from i back to i.
Hence, to detect negative cycles using the Floyd–Warshall algorithm,
one can inspect the diagonal of the path matrix, and the presence of a
negative number indicates that the graph contains at least one negative
cycle.[2] Obviously, in an undirected graph a negative edge creates a
negative cycle (i.e., a closed walk) involving its incident vertices
 PATH RECONSTRUCTION
The Floyd–Warshall algorithm typically only provides the lengths of the
paths between all pairs of vertices. With simple modifications, it is
possible to create a method to reconstruct the actual path between any
two endpoint vertices. While one may be inclined to store the actual path
from each vertex to each other vertex, this is not necessary, and in fact,
is very costly in terms of memory. For each vertex, one need only store
the information about which vertex one has to go through if one wishes
to end up at any given vertex. Therefore, information to reconstruct all
paths can be stored in an single N×N matrix 'next' where next[i][j]
represents the vertex one must travel through if one intends to take the
shortest path from i to j. Implementing such a scheme is trivial as when a
new shortest path is found between two vertices, the matrix containing
the paths is updated. The next matrix is updated along with the path
matrix such that at completion both tables are complete and accurate,
and any entries which are infinite in the path table will be null in the
next table. The path from i to j is then path from i to next[i][j], followed
by path from next[i][j] to j. These two shorter paths are determined
recursively. This modified algorithm runs with the same time and space
complexity as the unmodified algorithm.
 APPLICATIONS AND GENERALIZATIONS
The Floyd–Warshall algorithm can be used to solve the following
problems, among others:

 Shortest paths in directed graphs (Floyd's algorithm).

 Transitive closure of directed graphs (Warshall's algorithm). In
Warshall's original formulation of the algorithm, the graph is
unweighted and represented by a Boolean adjacency matrix. Then the
addition operation is replaced by logical conjunction (AND) and the
minimum operation by logical disjunction (OR).
 Finding a regular expression denoting the regular
language accepted by a finite automaton (Kleene's algorithm)
 Inversion of real matrices (Gauss–Jordan algorithm)[citation needed].
 Optimal routing. In this application one is interested in finding the
path with the maximum flow between two vertices. This means that,
rather than taking minima as in the pseudocode above, one instead
takes maxima. The edge weights represent fixed constraints on flow.
Path weights represent bottlenecks; so the addition operation above is
replaced by the minimum operation.
 Testing whether an undirected graph is bipartite.
 Fast computation of Pathfinder networks.
 Maximum Bandwidth Paths in Flow Networks
 PRISM ALGORITHM
INTRODUCTION
In computer science, Prim's algorithm is a greedy algorithm that finds
a minimum spanning tree for a connected weighted undirected graph.
This means it finds a subset of the edges that forms a tree that includes
every vertex, where the total weight of all the edges in the tree is
minimized. The algorithm was developed in 1930
by Czech mathematician Vojtěch Jarník and later independently
by computer scientistRobert C. Prim in 1957 and rediscovered by Edsger
Dijkstra in 1959. Therefore it is also sometimes called the DJP
algorithm, the Jarník algorithm, or the Prim–Jarník algorithm

DESCRIPTION
Prim's algorithm has many applications, such as in the generation of this
maze, which involves a randomized variant of Prim's algorithm.
The only spanning tree of the empty graph (with an empty vertex set) is
again the empty graph. The following description assumes that this
special case is handled separately.
The algorithm continuously increases the size of a tree, one edge at a
time, starting with a tree consisting of a single vertex, until it spans all
vertices.Input: A non-empty connected weighted graph with
vertices V and edges E (the weights can be negative).

 Initialize: Vnew = {x}, where x is an arbitrary node (starting point)

from V, Enew = {}
 Repeat until Vnew = V:
  Choose an edge (u, v) with minimal weight such that u is
in Vnew and v is not (if there are multiple edges with the same
weight, any of them may be picked)
 Add v to Vnew, and (u, v) to Enew
 Output: Vnew and Enew describe a minimal spanning tree

TIME COMPLEXITY

Minimum edge weight data

Time complexity (total)
structure

adjacency matrix, searching O(V2)

O((V + E) log(V)) = O(E

binary heap and adjacency list
log(V))

Fibonacci heap and adjacency list O(E + V log(V))

 EXAMPLE RUN

Image Description

This is our original weighted graph. The

numbers near the edges indicate their weight.

Vertex D has been arbitrarily chosen as a

starting point. Vertices A, B, E and F are
connected to D through a single edge. A is the
vertex nearest to D and will be chosen as the
second vertex along with the edge AD.

The next vertex chosen is the vertex nearest

to either D or A. B is 9 away from D and 7 away
from A, E is 15, and F is 6. F is the smallest
distance away, so we highlight the vertex F and
the arc DF.
The algorithm carries on as above. Vertex B,
which is 7 away from A, is highlighted.

In this case, we can choose between C, E,

and G. C is 8 away from B, E is 7 away from B,
and G is 11 away from F. E is nearest, so we
highlight the vertex Eand the arc BE.

Here, the only vertices available

are C and G. C is 5 away from E, and G is 9
away from E. C is chosen, so it is highlighted
along with the arc EC.

Vertex G is the only remaining vertex. It is 11

away from F, and 9 away from E. E is nearer, so
we highlight it and the arc EG.
Now all the vertices have been selected and
the minimum spanning tree is shown in green. In
this case, it has weight 39.
 KRUSKAL’S ALGORITHM
INTRODUCTION
Kruskal's algorithm is an algorithm in graph theory that finds
a minimum spanning tree for a connected weighted graph. This means it
finds a subset of the edges that forms a tree that includes every vertex,
where the total weight of all the edges in the tree is minimized. If the
graph is not connected, then it finds a minimum spanning forest (a
minimum spanning tree for each connected component). Kruskal's
algorithm is an example of a greedy algorithm.
This algorithm first appeared in Proceedings of the American
Mathematical Society, pp. 48–50 in 1956, and was written by Joseph
Kruskal.
Other algorithms for this problem include Prim's algorithm, Reverse-
Delete algorithm, and Borůvka's algorithm.

DESCRIPTION
 create a forest F (a set of trees), where each vertex in the graph is a
separate tree
 create a set S containing all the edges in the graph
 while S is nonempty and F is not yet spanning
 remove an edge with minimum weight from S
 if that edge connects two different trees, then add it to the
forest, combining two trees into a single tree
 otherwise discard that edge.
At the termination of the algorithm, the forest has only one component
and forms a minimum spanning tree of the graph.
 PERFORMANCE
Where E is the number of edges in the graph and V is the number of
vertices, Kruskal's algorithm can be shown to run in O(E log E) time, or
equivalently, O(E log V) time, all with simple data structures. These
running times are equivalent because:

 E is at most V2 and logV2 = 2logV  is O(log V).

 If we ignore isolated vertices, which will each be their own
component of the minimum spanning forest, V ≤ E+1, so
log V is O(log E).
We can achieve this bound as follows: first sort the edges by weight
using a comparison sort in O(E log E) time; this allows the step "remove
an edge with minimum weight from S" to operate in constant time. Next,
we use a disjoint-set data structure (Union&Find) to keep track of which
vertices are in which components. We need to perform O(E) operations,
two 'find' operations and possibly one union for each edge. Even a
simple disjoint-set data structure such as disjoint-set forests with union
by rank can perform O(E) operations in O(E log V) time. Thus the total
time is O(E log E) = O(E log V).
Provided that the edges are either already sorted or can be sorted in
linear time (for example with counting sort or radix sort), the algorithm
can use more sophisticated disjoint-set data structure to run in O(E α(V))
time, where α is the extremely slowly-growing inverse of the single-
valued Ackermann function.
 EXAMPLE

Image Description

This is our original graph. The numbers near the

arcs indicate their weight. None of the arcs are
highlighted.

AD and CE are the shortest arcs, with length 5,

and AD has been arbitrarily chosen, so it is
highlighted.

CE is now the shortest arc that does not form a

cycle, with length 5, so it is highlighted as the
second arc.
The next arc, DF with length 6, is highlighted
using much the same method.

The next-shortest arcs are AB and BE, both with

length 7. AB is chosen arbitrarily, and is
highlighted. The arc BD has been highlighted in
red, because there already exists a path (in
green) between Band D, so it would form a
cycle (ABD) if it were chosen.

The process continues to highlight the next-

smallest arc, BE with length 7. Many more arcs
are highlighted in red at this stage: BC because
it would form the loop BCE, DE because it
would form the loop DEBA, and FE because it
would form FEBAD.

Finally, the process finishes with the arc EG of

length 9, and the minimum spanning tree is
found.
 PROOF OF CORRECTNESS
The proof consists of two parts. First, it is proved that the algorithm
produces a spanning tree. Second, it is proved that the constructed
spanning tree is of minimal weight.
Spanning tree
Let P be a connected, weighted graph and let Y be the subgraph
of P produced by the algorithm. Y cannot have a cycle, since the last
edge added to that cycle would have been within one subtree and not
between two different trees. Ycannot be disconnected, since the first
encountered edge that joins two components of Y would have been
added by the algorithm. Thus, Y is a spanning tree of P.
Minimality
We show that the following proposition P is true by induction: If F is the
set of edges chosen at any stage of the algorithm, then there is some
minimum spanning tree that contains F.

 Clearly P is true at the beginning, when F is empty: any minimum

spanning tree will do, and there exists one because a weighted
connected graph always has a minimum spanning tree.
 Now assume P is true for some non-final edge set F and let T be a
minimum spanning tree that contains F. If the next chosen edge e is
also in T, then P is true for F + e. Otherwise, T + e has a cycle C and
there is another edge f that is in C but not F. (If there were no such
edge f, then e could not have been added to F, since doing so would
have created the cycle C.) Then T − f + e is a tree, and it has the same
weight as T, since T has minimum weight and the weight off cannot
be less than the weight of e, otherwise the algorithm would have
chosen f instead of e. So T − f + e is a minimum spanning tree
containing F + e and again P holds.
 Therefore, by the principle of induction, P holds when F has
become a spanning tree, which is only possible if F is a minimum
spanning tree itself.