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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC) Capitolo o saggio
Graph algorithms, shortest path, maximum flow, minimum spanning tree, travelling salesman problem
English
Encyclopedia of Bioinformatics and Computational Biology : ABC of Bioinformatics. Vol.1: Methods
Ranganathan, S; Gribskov, M; Nakai, K; Schönbach, C (Editors in Chief)
2019
9780128114148
1
Elsevier
940
949
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].
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/197343`
##### Citazioni
• 6
• ND