In this paper, we report on our own experience in studying a fundamental problem on graphs: all pairs shortest paths. In particular, we discuss the interplay between theory and practice in engineering a simple variant of Dijkstra's shortest path algorithm. In this context, we show that studying heuristics that are efficient in practice can yield interesting clues to the combinatorial properties of the problem, and eventually lead to new theoretically efficient algorithms.
Engineering shortest path algorithms / Demetrescu, Camil; Giuseppe F., Italiano. - 3059:(2004), pp. 191-198. (Intervento presentato al convegno 3rd International Workshop on Experimental and Efficient Algorithms tenutosi a Angra dos Reis, BRAZIL) [10.1007/978-3-540-24838-5_14].
Engineering shortest path algorithms
DEMETRESCU, Camil;
2004
Abstract
In this paper, we report on our own experience in studying a fundamental problem on graphs: all pairs shortest paths. In particular, we discuss the interplay between theory and practice in engineering a simple variant of Dijkstra's shortest path algorithm. In this context, we show that studying heuristics that are efficient in practice can yield interesting clues to the combinatorial properties of the problem, and eventually lead to new theoretically efficient algorithms.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
