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.

Problema[modifica | modifica sorgente]

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 sotto forma di numero reale: f: ER) e dato inoltre un elemento (vertice) v di V, trovare un cammino P da v ad un altro distinto v' di V in modo che

\sum_{p\in P} f(p)

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' .

Soluzione[modifica | modifica sorgente]

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.

Fonti[modifica | modifica sorgente]


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica