Açıklaması şöyle
Find the subtree of the input graph that minimizes the total weight of its edges.
Prim- Dijkstra algorithm
Açıklaması şöyle
In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by Dijkstra's algorithm. However, he also poses another problem, namely that of constructing the tree of minimum total length between the n nodes of the connected graph.
Açıklaması şöyle
The algorithm here suggested by Dijkstra is today known as Prim's algorithm.
Kruskal's algorithm
Açıklaması şöyle
Kruskal's algorithm works as follows:- sort the edges by increasing weight- repeat: pop the cheapest edge, if it does not create cycles, include it in the MST
Hiç yorum yok:
Yorum Gönder