使用Dijkstra的找到一个最小生成树？ [英] Use Dijkstra's to find a Minimum Spanning Tree?

问题描述

Dijkstra的的通常用于找到在两个节点之间的最短距离图形。它可以用来寻找最小生成树？如果是这样，怎么样？

Dijkstra's is typically used to find the shortest distance between two nodes in a graph. Can it be used to find a minimum spanning tree? If so, how?

编辑：这不是功课，但我想了解在一个旧练习考试的问题

This isn't homework, but I am trying to understand a question on an old practice exam.

推荐答案

严格来说，答案是否定的。 Dijkstra算法发现2个顶点上的曲线图之间的最短路径。然而，一个非常小的变化的算法产生另一种算法，并有效地产生MST。

Strictly, the answer is no. Dijkstra's algorithm finds the shortest path between 2 vertices on a graph. However, a very small change to the algorithm produces another algorithm which does efficiently produce an MST.

的算法设计手册是最好的书，我发现来回答类似这样的问题。

The Algorithm Design Manual is the best book I've found to answer questions like this one.

这篇关于使用Dijkstra的找到一个最小生成树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！