Топ-100
Indietro

ⓘ Cammino minimo. Nella teoria dei grafi, il cammino minimo tra due vertici di un grafo è quel percorso che collega i suddetti vertici e che minimizza la somma de ..




Cammino minimo
                                     

ⓘ Cammino minimo

Nella teoria dei grafi, il cammino minimo tra due vertici di un grafo è quel percorso che collega i suddetti vertici e che minimizza la somma dei costi associati allattraversamento di ciascun arco.

                                     

1. 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 {\displaystyle V} di vertici, un insieme E {\displaystyle E} di archi e una funzione che associ a ciascun lato un costo sotto forma di numero reale: f: E → R {\displaystyle f:E\rightarrow \mathbb {R} } e dati inoltre due vertici distinti v, v ′ ∈ V {\displaystyle v,v\prime \in V}, trovare un cammino P = {\textstyle P=e_{v,v_{2}},e_{v_{2},v_{3}},\ldots,e_{v_{n},v\prime }} da v {\displaystyle v} a v ′ {\textstyle v\prime } che, tra tutti quelli che collegano i vertici v {\displaystyle v} e v ′ {\textstyle v\prime }, minimizzi la somma ∑ e ∈ P f e {\displaystyle \sum _{e\in P}fe}.

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.

Unaltra applicazione di questo problema è presente nel gioco dei Sei gradi di separazione che tenta di dimostrare che ogni persona è connessa ad unaltra persona casuale attraverso un percorso di conoscenze con non più di 5 intermediari.

                                     

2. 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 Johnson - risolve tutte le coppie, può essere più veloce dellalgoritmo di Floyd-Warshall su grafi sparsi
  • Algoritmo A* - risolve problemi con una sola sorgente usando leuristica per tentare di velocizzare la ricerca
  • Algoritmo di Floyd-Warshall - risolve tutte le possibili coppie
  • Algoritmo di Bellman-Ford - risolve problemi con una sola sorgente, anche se i pesi degli archi sono negativi
  • 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 desecuzione, questo algoritmo può infatti calcolare la strada più breve da un determinato nodo di partenza "p" e tutti gli altri nodi del grafo.
                                     
  • topologico X Cammino casuale Cammino euleriano Cammino hamiltoniano Cammino libero medio Cammino libero medio anaelastico Cammino minimo Cammino spirituale
  • il minimo e si segue il percorso inverso per arrivare al cammino minimo Data una qualsiasi casella è facile vedere che q i, j è uguale al minimo costo
  • è la ricerca del cammino minimo tra due vertici in un grafo, come illustrato nella figura accanto: prima si trova il cammino minimo dal vertice di arrivo
  • rimuovendo il vincolo di capacità, il MCFP viene ridotto al problema del cammino minimo se tutti i costi vengono impostati uguali a zero, il MCFP viene ridotto
  • Il Cammino Portoghese è uno tra i percorsi che compongono il Cammino di Santiago di Compostela. Lungo circa 630 km, inizia a Lisbona, per raggiungere
  • Dijkstra, per determinare il cammino minimo per raggiungere ogni nodo della rete ponendosi come radice dell albero dei cammini minimi Al termine della elaborazione
  • dato un grafo con archi pesati, l albero ricoprente minimo o albero di copertura di costo minimo minimum spanning tree, MST è un albero ricoprente nel
  • totale del cammino la somma dei pesi sugli archi percorsi per arrivare al nodo i - esimo e J i che indica il nodo che precede i nel cammino minimo Inoltre
  • permettono alle distanze minime di propagarsi accuratamente attraverso il grafo, poiché, in assenza di cicli negativi il cammino minimo può solo visitare ciascun