Gfrktyl

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 soppesato (cioè un insieme V{displaystyle V} di vertici, un insieme E{displaystyle E} di lati e una funzione che associ a ciascun lato un costo sotto forma di numero reale: f:E→R{displaystyle f:Erightarrow mathbb {R} }) e dati inoltre due vertici distinti v,v′∈V{displaystyle v,vprime in V}, trovare un cammino P=(ev,v2,ev2,v3,…,evn,v′){textstyle P=(e_{v,v_{2}},e_{v_{2},v_{3}},ldots ,e_{v_{n},vprime })} da v{displaystyle v} a v′{textstyle vprime } che, tra tutti quelli che collegano i vertici v{displaystyle v} e v′{textstyle vprime }, minimizzi la somma ∑e∈Pf(e){displaystyle sum _{ein 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.

Portale Informatica

Portale Matematica