Cammino minimo

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Shortest path)

Nella teoria dei grafi, il cammino minimo (o shortest path) tra due vertici (o nodi) di un grafo è quel percorso che collega i suddetti vertici e che minimizza la somma dei costi associati all'attraversamento di ciascun arco (o lato).

Problema[modifica | modifica wikitesto]

Il problema della ricerca del cammino minimo può essere definito sia su grafi orientati che su grafi non orientati. Esso può essere così formalizzato: dato un grafo soppesato (cioè un insieme V di vertici, un insieme E di lati e una funzione che associ a ciascun lato un costo sotto forma di numero reale: f:E\rightarrow \mathbb{R}) e dati inoltre due vertici distinti v,v\prime\in V, trovare un cammino {\textstyle P=(e_{v,v_2},e_{v_2,v_3},\ldots,e_{v_n,v\prime}) } da v a {\textstyle v\prime } che, tra tutti quelli che collegano i vertici v e {\textstyle v\prime }, minimizzi la somma \sum_{e\in P} f(e).

Di questo problema esistono alcune varianti in cui, partendo da un dato vertice, può essere richiesto di trovare i cammini minimi verso tutti gli altri vertici; oppure trovare i cammini minimi per ogni coppia di vertici del grafo.

Un problema simile è 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 è però 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 è presente nel gioco dei Sei gradi di separazione che tenta di dimostrare che ogni persona è connessa ad un'altra persona casuale attraverso un percorso di conoscenze con non più di 5 intermediari.

Soluzione[modifica | modifica wikitesto]

Una soluzione al problema del cammino minimo è ottenuta attraverso gli "algoritmi 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 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

Bibliografia[modifica | modifica wikitesto]

Controllo di autorità GND: (DE4138403-9