Dijkstra를 사용하여 최소 스패닝 트리를 찾으십니까?

Question

Dijkstra 's 일반적으로 그래프에서 두 노드 사이의 가장 짧은 거리를 찾는 데 사용됩니다. 최소를 찾는 데 사용할 수 있습니다 스패닝 트리? 그렇다면 어떻게?

편집 : 이것은 숙제가 아니지만 구식 시험에서 질문을 이해하려고 노력하고 있습니다.

Answer 1

엄격히 대답은 아니오입니다. Dijkstra의 알고리즘은 그래프에서 2 개의 정점 사이에서 가장 짧은 경로를 찾습니다. 그러나 알고리즘에 대한 매우 작은 변화는 MST를 효율적으로 생성하는 또 다른 알고리즘을 생성합니다.

알고리즘 디자인 매뉴얼 내가 이런 질문에 대답하는 것이 가장 좋은 책입니다.

Answer 2

내 대답은 아니오 야. 이유를 확인하려면 먼저 다음과 같은 질문을 설명하겠습니다.

Q : 연결된, 무시되지 않은 가중치 그래프의 경우 G = (V, E, w) 음이없는 가장자리 가중치만으로 Dijkstra 알고리즘에 의해 생성 된 전임자 하위 그래프가 G의 최소 스패닝 트리를 형성합니까?

(지시되지 않은 그래프는 특별한 클래스의 지시 된 그래프이므로, 방향이없는 그래프에서 dijkstra 알고리즘을 사용하는 것은 완벽하게 괜찮습니다. 또한 MST는 연결되어 있지 않은 그래프에 대해서만 정의되며 그래프에 가중치가 없으면 사소합니다. 이 그래프에 대한 문의를 제한해야합니다.)

ㅏ: Dijkstra의 알고리즘 모든 단계마다 탐욕스럽게 일부에 가장 가까운 다음 가장자리를 선택합니다. 소스 vertex s. S가 그래프의 다른 모든 정점에 연결될 때 까지이 작업을 수행합니다. 분명히, 생산 된 전임자 하위 그래프는 스패닝 트리입니다. G, 그러나 가장자리 가중치의 합이 최소화됩니까?

Prim의 알고리즘, 최소 스패닝 트리를 생성하는 것으로 알려진 것은 Dijkstra의 알고리즘과 매우 유사하지만 각 단계에서 가장 가까운 다음 가장자리를 탐욕스럽게 선택합니다. 현재 해당 단계의 MST에있는 모든 정점. 이 관찰을 사용하여 반례를 생성합시다.

반례 : 방향되지 않은 그래프를 고려하십시오 G = (V, E, w) 어디

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

가져가다 a 소스 vertex로.

Dijkstra의 알고리즘은 가장자리를 취합니다 { (a,b), (a,c), (a,d) }.
따라서이 스패닝 트리의 총 중량은 5 + 5 + 5 = 15.

Prim의 알고리즘은 가장자리를 취합니다 { (a,d), (b,d), (c,d) }.
따라서이 스패닝 트리의 총 중량은 5 + 1 + 1 = 7.

Answer 3

Prim의 알고리즘 Dijkstra의 알고리즘과 동일한 기본 원리를 사용합니다.

Answer 4

나는 Prim 's 또는 Kruskal's와 같은 욕심 많은 알고리즘을 유지하고 있습니다. 나는 Djikstra가하지 않을 것을 두려워합니다. 단순히 나무 전체가 아닌 노드 쌍 사이의 비용을 최소화하기 때문입니다.

Answer 5

물론 최소 스패닝 트리에 dijkstra를 사용할 수 있습니다.

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

스패닝 트리에 Dijkstra를 사용하는 예는 다음과 같습니다.

알고리즘의 기초 책, 4 장, 섹션 2에 대한 추가 설명을 찾을 수 있습니다.

이 도움을 바랍니다