Cammino minimo
# 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 $P=(e_{v, v2},$ $e_{v2, v3},$ …, $e_{vn, v′}){\textstyle$ P=(e_{v, v_{2}}, e_{v_{2}, v_{3}}, \ldots , e_{v_{n}, v\prime })} da $v$ a v′{\textstyle v\prime } che, tra tutti quelli che collegano i vertici $v$ e v′{\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
