Graph Algorithms

We consider the main graph algorithms that are applied in several fields, from transport network to computational biology. We start by describing two algorithms for graph visit (depth-first search and breadth-first search). Then, we present different algorithms for the computation of shortest paths between two vertices: Dijkstra׳s algorithm, Bellman-Ford algorithm, and Floyd-Warshall. We then consider the flow in a graph for which we present the well-known Ford-Fulkerson algorithm. We describe two algorithms for finding a minimum spanning tree in a graph, Kruskal׳s algorithm and Prim׳s algorithm. We conclude this contribution presenting the traveling salesman problem and a computational approach to deal with it, the nearest neighbor algorithm.