International Collegiate Programming
Contest

Basic Graph Algorithms
This session focuses on graphs and basic graph algorithms. If you are not
familiar with the relevant concepts and algorithms, or you need a refresher,
you can use the resources below.
Problem Set

Arctic Network

Island Hopping

Nikola

Reachable Roads

Single source shortest path, negative weights
Note: All problems expect I/O to be done using standard input and standard
output. The solution to problems must be written in a single file.
If you are programming in Java the application class should be called
"Main" and should be in the default package.
The graphs here are collections of vertices, joined by (possibly directed,
possibly weighted) edges. For notions
like neighborhoods, paths, cycles, connectedness, trees, and so on,
the Glossary of graph theory on Wikipedia
is a good source of information.
This Topcoder tutorial
has some information on the representation of graphs, as does
this Wikipedia page.
The basic algorithmic procedures that are most relevant for the ICPC include:
 graph traversal,
 finding connected components,
 finding shortest paths, and
 finding minimum spanning trees.
Graph Traversal
There are two basic types of searches in a graph:
breadthfirst search (BFS)
and depthfirst search (DFS).
Both of them produce a spanning tree/forest on
undirected graphs. This
Topcoder tutorial
discusses the implementation of these searches, with examples.
Connectivity
One important notion for solving problems involving graphs is that of
connected components.
Connected components can be computed using depthfirst or
breadthfirst search. It might be necessary to keep track of
additional information, such as the number of vertices in the subtrees of the
BFS or DFS trees.
Sometimes one has to keep track of this information as a graph
is dynamically generated, e.g., in the
unionfind algorithm.
Shortest Paths
Often, a graph is weighted, with each edge having a real number (often
positive) as some sort of cost associated with it. The classic example is of
a network of roads joining cities, with the weight of each edge being the
length of the corresponding road. A natural problem is to find a
shortest path
between two vertices on the graph. There are a number of algorithms for
finding shortest paths. Three important ones are
Dijkstra's algorithm, BellmanFord, and FloydWarshall.
 Dijkstra and BellmanFord
Dijkstra's algorithm
finds, for a given source vertex, the length of a shortest path from it to
each other vertex in the graph, provided that all edge weights are nonnegative.The
Wikipedia page for Dijkstra's Algorithm
explains the basic algorithm, and
this Topcoder tutorial
discusses how to implement Dijkstra's algorithm efficiently using a priority
queue. A naive implementation of Dijkstra's Algorithm runs in O(V^{2}) time,
where V is the number of vertices. More sophisticated implementations
(using a priority queue) give a runtime of O(ElogV) or even O(E+VlogV),
(here, E is the number of edges) which is significantly better if the graph is
sparse (has far fewer than V^2 edges). Note that Dijkstra's
algorithm can fail if the graph has edges with negative weights. In that case,
a different algorithm, such as
BellmanFord,
can be used.
 FloydWarshall
The FloydWarshall algorithm finds out more information: shortest paths
between every pair of nodes in the graph. Of course, this is at the cost of
running time  the FloydWarshall algorithm runs in O(V^3) time. The
Wikipedia article for FloydWarshall
has more information.
Two observations.
One oftenuseful special case is when all the edge weights are equal to 1.
In this case, there is an even easier and faster algorithm  breadthfirst
search, which runs in linear time! Just keep track of how far you are from
your starting vertex when you first reach each vertex.
Another important observation is the following: the simplest versions of
these algorithms only find the length of a shortest path.
If you want an actual shortest path and not just its length, you
need to keep track of enough information to allow you to extract it!
Fortunately, this is not difficult to do and doesn't significantly increase
the running time of the algorithms.
Minimum Spanning Trees
Another important notion is that of a
minimum spanning tree.
If a graph is connected, there is guaranteed to be at least one tree which
is a subgraph of the original graph and contains every vertex; this is a
spanning tree. In a weighted graph, a minimum spanning tree is a spanning
tree with the minimum possible (over all spanning trees) sum of edge weights.
 Prim
Prim's algorithm
builds a minimum spanning tree by starting with an arbitrary vertex,
and grows a tree by greedily connecting new vertices to the existing subtree.
The resulting code is very similar to the one for Dijkstra's
algorithm.
 Kruskal
Kruskal's
algorithm iterates over the edges from smallest to largest weight, and
includes an edge unless it creates a cycle. The subgraph may only become
connected at the very end. On order to implement Kruskal efficiently, one
uses an efficient unionfind data structure to keep track of the connected
components of the subgraph constructed thus far.
