Shortest path

Da Wikipedia, l'enciclopedia libera.

Lo shortest path è, nella teoria dei grafi, il cammino minimo tra due vertici, ossia quel percorso che collega due vertici dati e che minimizza la somma dei costi associati all'attraversamento di ciascun lato.

Indice 1 Problema 2 Soluzione 3 Fonti 4 Collegamenti esterni

[modifica] Problema

Più formalmente il problema dello shortest path si può enunciare così: dato un grafo soppesato (cioè un insieme V di vertici, un insieme E di lati e una funzione che restituisca il costo sottoforma di numero reale: f: E → R) e dato inoltre un elemento (vertice) v di V, trovare un cammino P da v a ciascun v' di V in modo che

sia la minima tra tutte quelle relative ai cammini che collegano v a v' . Il problema dello shortest path per tutte le coppie è simile. In tal caso bisogna trovare percorsi siffatti per ogni coppia di vertici v-v' .

[modifica] Soluzione

Una soluzione al problema dello shortest path è quello che viene chiamato un "algoritmo di tracciamento (di rotta)" (pathing algorithm). I più importanti algoritmi di questa categoria sono :

• Algoritmo di Dijkstra - risolve problemi con una sola sorgente se tutti i pesi degli archi sono maggiori o uguali a zero. Senza richiedere un elevato tempo d'esecuzione, questo algoritmo può infatti calcolare la strada più breve da un determinato nodo di partenza "p" e tutti gli altri nodi del grafo.
• Algoritmo di Bellman-Ford - risolve problemi con una sola sorgente, anche se i pesi degli archi sono negativi
• Algoritmo di ricerca A* - risolve problemi con una sola sorgente usando l'euristica per tentare di velocizzare la ricerca
• Algoritmo di Floyd-Warshall - risolve tutte le possibili coppie
• Algoritmo di Johnson - risolve tutte le coppie, può essere più veloce dell'algoritmo di Floyd-Warshall su grafi sparsi

Un problema simile a questo è quello del commesso viaggiatore, in cui si cerca il percorso più breve che attraversi tutti i nodi del grafo una sola volta, per poi ritornare al punto di partenza. Questo problema è NP-Completo, per cui una soluzione efficiente potrebbe non esistere.

Nel campo delle telecomunicazioni, questo problema viene a volte chiamato min-delay path problem.

Un'altra applicazione di questo problema è il gioco dei Sei gradi di separazione che tenta di trovare il percorso più breve che unisce attori apparsi nello stesso film.

[modifica] Fonti

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Seconda Edizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capitoli 24: Single-Source Shortest Paths, e 25: All-Pairs Shortest Paths, pp.580-642.

[modifica] Collegamenti esterni

• Shoes, gioco che consente di creare grafi dinamici per testare un robot che trova lo shortest path.
• Sei gradi di Wikipedia, un query solver di shortest path sulla Wikipedia inglese. Come collegare due voci qualunque con meno di 6 wikilink.