Graph Algorithms

Graphs are a widely used model to describe structural relations. They are built of nodes, which are connected by edges (both directed or undirected). Some prominent examples for the application of graphs are:
  • Routing
    In this case nodes represent important places (junctions, cities), while edges correspond to roads connecting these places. A one-way road is represented by a directed edge.
  • Communication networks (i.e. phone networks or internet)
    Here, nodes are phones, modems, server, ISPs and more, edges are data lines connecting them.
  • Gantt diagrams for sequence planning
    Nodes correspond to phases of the projets, directed edges to dependencies between sections.
  • Representation of hierarchical structures

Handling such models with means of algorithmic graph theory is an important area of mathematics and computer science. Some important algorithms of this area shall be presented and explained in the following, both by an interactive applet as well as by their pseudocode.

One of the application of graphs in everyday life used most is the representation of infrastructure and communication networks. A map of the German highways, bus lines in a city or the flights offered by an airline; they all are depicted by a graph without us noticing it at all.

In this context it is obvious that the search of paths in the respective graphs is of great importance. Especially the "most benefical" path are very interesting. Thereby, "most benefical" can have diverse interpretations: Maybe it is the shortest of fastest way, eventually the cheapest or one that avoids the most speed checks.

Logo Dijkstra.png Dijkstra's Algorithm
Dijkstra's Algorithm computes the shortest path between two points whenever all adge weights are non-negative.

Logo AStar.png A* Algorithm
The A* Algorithm works similarly to Dijkstra's Algorithm. However, it uses an additional heuristic for the distance between nodes and thus is normally faster.

Logo BellmanFord.png Bellman-Ford Algorithm
In contrast to the former two algorithms, the Bellman-Ford Algorithm also return shortest paths when negative edge weights are present.

Logo FloydWarshall.png Floyd-Warshall Algorithm
The Floyd-Warshall Algorithm computes shortest paths between all pairs of points. It also works with negative edge weights.

The Minimal Spanning Tree Problem aims at connecting a set of nodes at minimal cost. Such problems are on hand if for example one wants to
  • connect some server at minimal cost or
  • supply some houses of a block with water by a pipeline network of minimal distance.

A Spanning Tree has to fulfill two characteristics. It has to be
  • connected and
  • free of circles.
One can then immediatly deduce that a spanning tree has to contain one edge less than the number of nodes. If he had less edges, he could not connect all nodes; if he had more, he had to contain a cycle.

If every edge has an associated weight – for example length or cost –, one can ask for a spanning tree of minimal total length or cost, i.e. for a Minimal Spanning Tree.

There are several algorithms that can compute minimal spanning trees, some of them discovered independently and even more than once. We restrict ourselves to two variants:

Logo Kruskal Prim.png Prim's Algorithm
Prim's Algorithm computes a minimal spanning tree on an undirected graph.

Logo Kruskal Prim.png Kruskal's Algorithm
Kruskal's Algorithm also computes a minimal spanning tree on an undirected graph. Furthermore, it returns a minimal spanning forest if the graph was unconnected.

The Matching Problem deals with the search of a relation of maximal size that connects two elements of different sets.

The Weighted Matching Problem is a special case that gives preferences to different relations in order to obtain the best allocation possible. It can be explained by the following example: The origin of the problem lies in the simple question of how to distribute presents among a certain number of children while obtaining optimal satisfaction.

Another typical problem is the so-called traditional "Marriage Problem", in which the subsets are occupied by women and men. The question arising is how to combine the couples in order to achieve a maximal satisfaction (low divorce rate).

This problem can be solved by the Hungarian Method (in the bipartite case) or the Blossom Algorithm (in the non-bipartite case, in the following presented for the unweighted problem).

Logo HopcroftKarp.png Hopcroft-Karp Algorithm
The Hopcroft-Karp Algorithm computes for two given sets with possible assignments a maximal relation.

Logo Hungarian.png Hungarian Method
The Hungarian Method determines for two given sets with weighted assignments a maximal (with respect to the weihts) relation.

Logo Blossom.png Blossom Algorithm
The Blossom Algorithm computes a maximal matching in an arbitrary graph (in contrast to the Hopcroft-Karp algorithm which requires a bipartite graph).

A very common problem in graphs and networks is the computation of flows. Be it the flow of goods, or information in a communication network, or flow in a pipeline network: the computation of flows in a network is a frequently modelled problem.

One often considers two variants:
  • When requesting a maximal flow, the amount of goods to be transported on an edge is bounded by its capacity. One then wants to yield the maximal flow possible between source and sink, given the capacities on the edges.
  • Alternatively, one might be interested in the cost-minimal flow of a given size. Besides edge capacities, the cost of transporting one unit of the good on an edge is given. In this case, the question is how to transport the required amount from source to sink while minimizing the transportation cost.

For both variants, there are many different algorithms. Two of them will be presented in the following.

Logo FordFulkerson.png Ford-Fulkerson Algorithm
The Ford-Fulkerson Algorithm computes the maximal flow in a network.

Logo CycleCancelling.png Cycle-Cancelling Algorithm
The Cycle-Cancelling Algorithm yields a maximal flow of minimal cost.

A classical problem of graph theory is the Eulerian Path Problem, which asks for paths or cycles that cover all arcs of a given graph.

The problem was first formulated by the following question:
The river Pregel divides the town Königsberg (Kaliningrad nowadays) in five parts, that are connected among themselves by seven bridges. Can one do a tour that passes each bridge exactly once?

This question can be interpreted and generalized as a graph theoretic problem (city parts as nodes, bridges as edges) and was thus solved by Leonhard Euler in 1736: Such a tour exists if and only if no or two nodes have odd degree.
If no nodes has odd degree, there is an Eulerian Cycle; if on the other hand two nodes have odd degree, only an Eulerian Path that starts and ends in different nodes is possible.

The aim of the related Chinese Postman Problem is to find a shortest path in a graph, such that this path uses each edge at least once and returns to the starting point.

The most prominent example for this problem is a postman that delivers mail in a part of his town. He has to visit each street once and he needs to return to the post office at the end, all while using as little time as possible. The problem's name originates exactly from the postman's problem and from the fact that it was first examined by a Chinese.
A similar example occurs for winter services: Each street has to be visited in order to remove snow, and each shift has to end at the depot where it started.

Logo Hierholzer.png Hierholzer Algorithm
The Hierholzer Algorithm computes an Eulerian Tour in a graph (if one exists).

Logo DirectedChinesePostman.png Chinese Postman Problem
The Chinese Postman Problem can be solved by combining the Matching Algorithms and the Hierholzer Algorithm presented above.