Algoritmo per trovare il percorso che minimizza il peso massimo tra due nodi

Question

Mi piacerebbe viaggiare in auto dalla città X alla città Y. La mia auto ha un piccolo serbatoio, e le stazioni di servizio esistono solo agli incroci delle strade (le intersezioni sono nodi e le strade sono bordi). Pertanto, vorrei prendere un percorso tale che la distanza massima che guido tra due stazioni di servizio sia ridotta al minimo. Quale algoritmo efficiente posso usare per trovare quel percorso? La forza bruta è una cattiva soluzione. Mi chiedo se esiste un algoritmo più efficiente.

Answer 1

Ecco una soluzione semplice:

1. Ordina i bordi di loro pesi.

2. Iniziare ad aggiungerli uno a uno (dal più leggero al più pesante) fino a quando X e Y diventano connessi.

3. Per verificare se sono collegati, è possibile utilizzare una struttura dati union-find.

La complessità del tempo è O(E log E).

Una prova di correttezza:

1. La risposta corretta non è più grande di quello restituito da questa soluzione. È il caso perché la soluzione è costruttiva: una volta che X e Y sono nello stesso componente, possiamo annotare esplicitamente il percorso tra di loro. Non può contenere bordi più pesanti perché non sono stati ancora aggiunti.

2. La risposta corretta non è inferiore a quella restituita da questa soluzione. Supponiamo che vi sia un percorso tra X e Y costituito da bordi che hanno un peso strettamente inferiore alla risposta restituita. Ma non è possibile poiché tutti i bordi più chiari sono stati elaborati prima (li abbiamo iterati nell'ordine ordinato) e X e Y erano in componenti diversi. Quindi, non c'era alcun percorso tra loro.

1) e 2) implicano la correttezza di questo algoritmo.

Questa soluzione funziona per i grafici non orientati.

Ecco un'algoritmi che risolve il problema per un caso diretto (funziona per grafi non orientati, anche):

1. Diamo ordinare i bordi dei loro pesi.

2. Eseguiamo la ricerca binaria sul peso del bordo più pesante nel percorso (è determinato da un indice del bordo nell'elenco ordinato di tutti i bordi).

3. Per una risposta candidato fisso i, siamo in grado di effettuare le seguenti operazioni:

   1. Aggiungi tutti i bordi con gli indici fino a i nella lista ordinata (vale a dire, tutti i bordi che non sono più pesanti di quello attuale uno).

   2. Eseguire DFS o BFS per verificare che vi sia un percorso da X a Y.

   3. Regola i bordi sinistro e destro nella ricerca binaria in base all'esistenza di tale percorso.

la complessità temporale è O((E + V) * log E) (corriamo DFS/BFS log E volte e ciascuno di essi è fatto in O(E + V) tempo).

Ecco un codice pseudo:

if (X == Y) 
    return 0 // We don't need any edges. 
if (Y is not reachable from X using all edges) 
    return -1 // No solution. 
edges = a list of edges sorted by their weight in increasing order 
low = -1 // definitely to small(no edges) 
high = edges.length - 1 // definitely big enough(all edges) 
while (high - low > 1) 
    mid = low + (high - low)/2 
    g = empty graph 
    for i = 0...mid 
     g.add(edges[i]) 
    if (g.hasPath(X, Y)) // Checks that there is a path using DFS or BFS 
     high = mid 
    else 
     low = mid 
return edges[high]