Utilice de Dijkstra para encontrar un árbol de expansión mínimo?

Question

de Dijkstra se suele utilizar para encontrar la distancia más corta entre dos nodos en un gráfico. ¿Se puede utilizar para encontrar un mínimo árbol de expansión ? Si es así, ¿cómo?

Editar:. Esta no es la tarea, pero estoy tratando de entender una pregunta en un examen de la práctica de edad

Answer 1

En sentido estricto, la respuesta es no. el algoritmo de Dijkstra encuentra el camino más corto entre 2 vértices en una gráfica. Sin embargo, un cambio muy pequeño en el algoritmo produce otro algoritmo que no producen eficazmente un MST.

El Manual de Diseño de Algoritmos es el mejor libro que he encontrado para la respuesta preguntas como ésta.

Answer 2

La respuesta es no. Para ver por qué, primero vamos a articular la pregunta de esta manera:

Q: Para una conectada,, G = (V, E, w) grafo ponderado no dirigido con pesos de las aristas solamente no negativos, ¿el subgrafo predecesor producida por el algoritmo de Dijkstra forman un árbol de expansión mínimo de G

?

(Tenga en cuenta que los gráficos no dirigidos son una clase especial de gráficos dirigidos, lo que es perfectamente aceptable utilizar el algoritmo de Dijkstra en los gráficos no dirigidos. Además, MST de se definen sólo para conectada, los gráficos no dirigidos, y son triviales si el gráfico no se pondera , por lo que debemos restringir nuestra consulta a estos gráficos.)

A: el algoritmo de Dijkstra a cada paso selecciona avidez el siguiente borde que está más cerca de algunos fuente vértice s . Esto se hace hasta que s está conectado a cada otro vértice en el gráfico. Claramente, el subgrafo predecesor que se produce es un árbol de expansión de G, sino que es la suma de pesos de las aristas minimizada?

Algoritmo de Prim , que se sabe que produce un árbol de expansión mínimo, es muy similar al algoritmo de Dijkstra, pero en cada etapa con avidez selecciona el siguiente borde que está más cerca cualquier vértice actualmente en el MST de trabajo en esa etapa . Vamos a utilizar esta observación para producir un contraejemplo.

Contraejemplo: Considerar el G = (V, E, w) grafo no dirigido donde

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 el vértice fuente.

El algoritmo de Dijkstra toma bordes { (a,b), (a,c), (a,d) }.
Por lo tanto, el peso total de este árbol de expansión es 5 + 5 + 5 = 15 .

Algoritmo de Prim tiene bordes { (a,d), (b,d), (c,d) }.
Por lo tanto, el peso total de este árbol de expansión es 5 + 1 + 1 = 7 .

Answer 3

algoritmo de Prim utiliza el mismo principio subyacente como el algoritmo de Dijkstra.

Answer 4

Me gustaría mantener a un algoritmo voraz, como Prim o de Kruskal. Temo Djikstra de que no va a hacer, simplemente porque minimiza el coste entre pares de nodos, no para todo el árbol.

Answer 5

Por supuesto, es posible utilizar Dijkstra para el árbol de expansión 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) ];
    }
}

A continuación se muestra un ejemplo de la utilización de Dijkstra para el árbol de expansión:

Se puede encontrar una explicación más detallada en el libro Fundamentos de Algoritmos, capítulo 4, sección 2.

Espero que esto ayuda