Rilasciato · in miglioramento
Algorithm
Calcolare cammini minimi con Dijkstra, Bellman-Ford e Floyd-Warshall e costruire alberi ricoprenti minimi con Kruskal e Prim.
Il problema del cammino minimo chiede, in un grafo pesato, il percorso con peso totale minimo tra due vertici. Un albero ricoprente minimo (MST) è l'insieme di archi più economico che collega tutti i vertici di un grafo non orientato senza formare cicli. Gli algoritmi centrali di questo argomento sono Dijkstra, Bellman-Ford, Floyd-Warshall, BFS 0-1, Kruskal e Prim.
Questi algoritmi lavorano nei navigatori, nei protocolli di routing come OSPF e RIP, nella ricerca di percorsi nei videogiochi, nella progettazione di reti di cavi e tubature e nel clustering. Sono anche un classico dei colloqui tecnici, perché mostrano se sai modellare un problema come grafo e scegliere l'algoritmo adatto ai pesi: negativi o no, solo 0 e 1, grafo sparso o denso.
Conviene prima prendere confidenza con la BFS e con le code di priorità (heap). Poi si studia il rilassamento, l'operazione comune a tutti gli algoritmi di cammino minimo, e si segue Dijkstra a mano su un piccolo grafo. Quindi si capisce perché gli archi negativi richiedono Bellman-Ford, si implementa Kruskal con union-find e si chiude con esercizi che eseguono Dijkstra su un grafo degli stati esteso.
Tutti gli algoritmi di cammino minimo si basano sul rilassamento, cioè verificare se passare per u accorcia il percorso verso v. Cambia solo l'ordine in cui rilassano gli archi.
Con pesi non negativi, un heap binario estrae e fissa ogni volta il vertice più vicino, ottenendo tutte le distanze da una sorgente in O((V + E) log V).
Bellman-Ford accetta archi negativi e rileva i cicli negativi; Floyd-Warshall calcola la distanza tra tutte le coppie di vertici in O(V^3).
Kruskal aggiunge gli archi dal più leggero al più pesante ed evita i cicli con union-find; Prim fa crescere un solo albero con l'arco uscente più economico. La proprietà del taglio garantisce che entrambi siano corretti.
heapq estrae le coppie (distanza, vertice) in ordine di distanza; una coppia con distanza maggiore di quella registrata è obsoleta e viene saltata. Quando la distanza di un vicino migliora, il codice la aggiorna e inserisce una nuova coppia. Eseguendo python dijkstra.py si stampano le distanze minime da A: {'A': 0, 'B': 3, 'C': 1, 'D': 4}.
dijkstra.py
import heapq
def dijkstra(graph, source):
dist = {source: 0}
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
python dijkstra.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Cammini minimi e alberi ricoprenti.
Fai domande, condividi la tua esperienza e scambia opinioni su Cammini minimi e alberi ricoprenti.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.