Use Dijkstra é para encontrar uma árvore mínima Spanning?

Question

de Dijkstra é normalmente usado para encontrar a distância mais curta entre dois nós em um gráfico. ele pode ser usado para encontrar um mínimo abrangendo árvore? Se sim, como?

Edit:. Esta não é a lição de casa, mas eu estou tentando entender uma pergunta em um exame de prática de idade

Answer 1

A rigor, a resposta é não. o algoritmo de Dijkstra encontra o caminho mais curto entre 2 vértices em um gráfico. No entanto, uma mudança muito pequena para o algoritmo produz um outro algoritmo que não produzir de forma eficiente uma MST.

O Manual Algoritmo Projeto é o melhor livro que eu encontrei para resposta perguntas como esta.

Answer 2

A resposta é não. Para ver por que, primeiro articulado Vamos a questão assim:

Q: Para um contacto, não dirigida, G = (V, E, w) grafo ponderado com pesos de borda única não negativos, é que o subgrafo predecessor produzida pelo Algoritmo de Dijkstra formar um mínimo árvore geradora de G

?

(Note que os gráficos sem direção são uma classe especial de grafos dirigidos, por isso é perfeitamente ok para usar o algoritmo de Dijkstra em gráficos sem direção. Além disso, do MST só são definidos para ligado, gráficos sem direção, e são triviais se o gráfico não é ponderada , por isso devemos restringir o nosso inquérito para estes gráficos.)

A: Algoritmo de Dijkstra em cada etapa avidamente seleciona a próxima borda que está mais próximo a alguns fonte vértice s . Ele faz isso até s está ligado a todos os outros vértices no gráfico. Claramente, o subgrafo predecessor que é produzido é uma árvore geradora de G, mas é a soma dos pesos das arestas minimizado?

O Prim Algoritmo , que é conhecido por produzir um mínimo abrangendo árvore, é muito semelhante ao algoritmo de Dijkstra, mas em cada etapa avidamente seleciona a próxima borda que está mais próximo qualquer vértice atualmente no MST trabalhando nessa fase . Vamos usar essa observação para produzir um contra-exemplo.

Contra-: Considere o gráfico G = (V, E, w) undirected onde

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 ) }

Tome a como o vértice fonte.

Algoritmo de Dijkstra leva bordas { (a,b), (a,c), (a,d) }.
Assim, o peso total deste Spanning Tree é 5 + 5 + 5 = 15 .

Algoritmo de Prim leva bordas { (a,d), (b,d), (c,d) }.
Assim, o peso total deste árvore de expansão é 5 + 1 + 1 = 7 .

Answer 3

de Prim algoritmo usa o mesmo princípio subjacente como o algoritmo de Dijkstra.

Answer 4

Eu manteria a um algoritmo guloso, como Prim ou Kruskal do. Temo Djikstra de não vai fazer, simplesmente porque ele minimiza o custo entre pares de nós, não para a árvore inteira.

Answer 5

É claro, é possível usar Dijkstra para árvore geradora mínima:

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) ];
    }
}

Aqui está um exemplo do uso de Dijkstra para árvore de expansão:

Você pode encontrar mais explicações em Fundamentos do livro Algorithms, capítulo 4, secção 2.

Espero que isso ajuda