In this contribution, 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.
Dondi, R., Mauri, G., Zoppis, I. (2019). Graph Algorithms. In S. Ranganathan, M. Gribskov, K. Nakai, C. Schönbach (a cura di), Encyclopedia of Bioinformatics and Computational Biology : ABC of Bioinformatics. Vol.1: Methods (pp. 940-949). Cambridge : Elsevier [10.1016/B978-0-12-809633-8.20424-X].
Graph Algorithms
Dondi, R;Mauri, G;Zoppis, I
2019
Abstract
In this contribution, 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
