Utilizzare di Dijkstra per trovare una Spanning Tree minima?
-
19-09-2019 - |
Domanda
di Dijkstra è in genere utilizzato per trovare la distanza più breve tra due nodi di un grafo. Può essere utilizzato per trovare un spanning tree ? Se sì, come?
Modifica:. Questo non è lavoro, ma sto cercando di capire una domanda su un esame vecchia pratica
Soluzione
In senso stretto, la risposta è no. L'algoritmo di Dijkstra trova il percorso più breve tra 2 vertici su un grafico. Tuttavia, una piccola modifica l'algoritmo produce un altro algoritmo che fa in modo efficiente produrre un MST.
Il manuale Algorithm design è il miglior libro che ho trovato per risposta domande come questa.
Altri suggerimenti
La risposta è no. Per capire perché, si deve prima articolare la questione in questo modo:
D: Per un collegamento, non orientato, pesata G = (V, E, w)
grafico con pesi bordo solo non negativi, non il sottografo predecessore prodotto dall'algoritmo di Dijkstra formano un albero di copertura minimo di G
?
(Notare che grafi non orientati sono una classe speciale di grafi orientati, quindi è perfettamente ok per utilizzare l'algoritmo di Dijkstra su grafi non orientati. Inoltre, MST di sono definiti solo collegato, grafi non orientati, e sono banali se il grafo non è ponderato , quindi dobbiamo limitare la nostra indagine a questi grafici.)
A: Algoritmo di Dijkstra seleziona ad ogni passo avidamente il bordo successivo che è più vicino a un vertice sorgente s . Ciò avviene fino s è collegato ad ogni altro vertice nel grafico. Chiaramente, il sottografo dei predecessori che viene prodotto è un albero di copertura di G
, ma è la somma dei pesi bordo minimizzato?
algoritmo di prim , che è noto per produrre un albero di copertura minimo, è molto simile all'algoritmo di Dijkstra, ma in ogni fase seleziona avidamente il bordo successivo che è più vicino al ogni vertice attualmente nel MST di lavoro in quella fase . Usiamo questa osservazione per produrre un controesempio.
Controesempio: Si consideri il grafo non orientato G = (V, E, w)
dove
V = { a, b, c, d }
E = { (a,b), (a,c), (a,d), (b,d), (c,d) }
w = {
( (a,b) , 5 )
( (a,c) , 5 )
( (a,d) , 5 )
( (b,d) , 1 )
( (c,d) , 1 )
}
Prendere a
come il vertice sorgente.
L'algoritmo di Dijkstra prende bordi { (a,b), (a,c), (a,d) }
.
Così, il peso totale di questa spanning tree è 5 + 5 + 5 = 15 .
Algoritmo di Prim prende bordi { (a,d), (b,d), (c,d) }
.
Così, il peso totale di questa spanning tree è 5 + 1 + 1 = 7 .
algoritmo di prim utilizza lo stesso principio di base come l'algoritmo di Dijkstra.
I terrei ad un algoritmo greedy come Prim del o Kruskal di. Temo Djikstra di non va bene, semplicemente perché minimizza il costo tra coppie di nodi, non per l'intero albero.
Naturalmente, è possibile utilizzare Dijkstra per l'albero di copertura minimo:
dijsktra(s):
dist[s] = 0;
while (some vertices are unmarked) {
v = unmarked vertex with
smallest dist;
Mark v; // v leaves “table”
for (each w adj to v) {
dist[w] = min[ dist[w], dist[v] + c(v,w) ];
}
}
Ecco un esempio di utilizzo di Dijkstra per spanning tree:
È possibile trovare ulteriori spiegazioni in Fondamenti di algoritmi libro, capitolo 4, sezione 2.
Spero che questo aiuto