Why the tree resulting from Kruskal is different from Dijkstra?

Question

Can anyone explain why the tree resulting from Kruskal is different from Dijkstra ?

I know for the fact that kruskal works on nondescending order of edges but Dijkstra takes advantage of priority queue but still cannot understand why the resulted tree from them are different?

Answer 1

The minimum spanning tree is not unique.

The Kruskal's algorithm select a minimum length edge of all possible edges which connect two different disjoint MST components, found so far.

The Dijkstra/Prim/Jarnik's algorithm selects minimum length edge of all the edges, which extend the single MST component found so far.

At each step, in the general case the algorithms select a minimum edge from distinct sets of possiblities.

PS. Well, if the OP refers to the shortest path tree of the Dijkstra's shortest path algorithm the answer is that the shortest path tree is not necessarily a minimum spanning tree, the algorithms compute different things.

Answer 2

The basic difference, I would say, is that given a set of nodes, Dijkstra's algorithm finds the shortest path between 2 nodes. Which does not necessarily cover all the nodes in the graph.

However on Kruskal's case, the algorithm tries to cover all the nodes while keeping the edge cost minimum.

Consider this graph:

       E
   3 / |
    B  | 3
 5 /3\ |
  /    D
A      | 2
  \    F
 1 \  / 1
    C
   2 \
      G

Dijkstra's algorithm will return the path A-C-F-D-E for source and destination nodes A and E, at a total cost of 7. However Kruskal's algorithm should cover all the nodes, therefore it will consider edges [AC], [CG], [CF], [FD], [DB] and [DE] with a total cost of 12.

In Dijkstra, the irrelevant nodes (ones that are not in the path from source the destination) are ignored, e.g., G and B in this case. The resulting path, of course, is a tree but does not cover all the nodes. There might be millions of nodes connected to G (assuming they are not connected to other nodes) which would not be in the path of the Dijkstra's result. On the other hand, Kruskal had to add those nodes to the resulting tree.

Answer 3

They solve different problems. It might be possible that they produce the same trees in some cases (e.g. the graph is already a tree), but in general the trees are optimized for different things: one finds the shortest paths from a single source, another minimizes the total weight of the tree.

For example, consider we built MST with Kruskall. Let's say all the edges in MST weight 1 and it looks more or less linear. Assume that to get from A to Z it takes 5 edges, so the path from A to Z in MST will cost 5. However, it might as well be possible that original graph had an edge from A to Z with cost 3 (< 5), which MST didn't include, yet Dijkstra will probably have the edge in its resulting tree.