Utilizzare di Dijkstra per trovare una Spanning Tree minima?

Question

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

Answer 1

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.

Answer 2

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 .

Answer 3

algoritmo di prim utilizza lo stesso principio di base come l'algoritmo di Dijkstra.

Answer 4

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.

Answer 5

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