Cammino minimo

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

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 pesato (cioè un insieme $V$ di vertici, un insieme $E$ di archi 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

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

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

Controllo di autorità	GND (DE) 4138403-9