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].
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Engineering shortest path algorithms | |
Autori: | ||
Data di pubblicazione: | 2004 | |
Serie: | ||
Citazione: | 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]. | |
Handle: | http://hdl.handle.net/11573/50579 | |
ISBN: | 9783540220671 9783540248385 | |
Appartiene alla tipologia: | 04b Atto di convegno in volume |