Graph Algorithms

In this article, we describe the main graph algorithms that are applied in several fields, from transport network to computational biology. First, we will review two-well known traversal algorithms (depth-first search and breadth-first search). Then we consider the problem of computing a shortest path between two vertices and we review the Dijkstra’s algorithm, the Bellman-Ford algorithm and Floyd-Warshall algorithm. Another fundamental graph problem we will deal with is that of computing a maximum flow in graph and we will review the Ford-Fulkerson algorithm for the computation of a maximum flow. Next, we will consider consider the computation of a minimum spanning tree of a given graph, and we will review two well-know algorithms for solving this problem: Kruskal’s algorithm and Prim’s algorithm. Finally, we will consider the traveling salesman problem and the nearest neighbour algorithm, which is a heuristic for this problem.