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.
(2019). Graph Algorithms . Retrieved from http://hdl.handle.net/10446/150356
Graph Algorithms
Dondi, Riccardo;
2019-01-01
Abstract
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.File | Dimensione del file | Formato | |
---|---|---|---|
EncyGraphAlgo2018.pdf
Solo gestori di archivio
Versione:
publisher's version - versione editoriale
Licenza:
Licenza default Aisberg
Dimensione del file
992.4 kB
Formato
Adobe PDF
|
992.4 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo