1. Introduction

In this tutorial, we’ll focus on two problems: Minimal Spanning Tree and Shortest Path Tree. We can solve both problems with greedy algorithms that have a similar structure.

2. Spanning Tree

A spanning tree of an undirected graph G is a connected subgraph that covers all the graph nodes with the minimum possible number of edges. In general, a graph may have more than one spanning tree.

The following figure shows a graph with a spanning tree. The edges of the spanning tree are in red:

3. Minimum Spanning Tree 

If the graph is edge-weighted, we can define the weight of a spanning tree as the sum of the weights of all its edges. A minimum spanning tree is a spanning tree whose weight is the smallest among all possible spanning trees. 

The following figure shows a minimum spanning tree on an edge-weighted graph:

We can solve this problem with several algorithms including Prim’s, Kruskal’s, and Boruvka’s. Let’s introduce Prim’s algorithm since it has a similar structure with the solution to the shortest path tree problem:

Rendered by QuickLaTeX.com

Visually, let’s run Prim’s algorithm for a minimum spanning tree on our sample graph step-by-step:

The time complexity of Prim’s algorithm depends on the data structures used for the graph.

For example, if we use the adjacency list to represent a graph and store the edges in a priority queue, the overall time complexity is O(E log V), where V is the number of nodes in the graph and E is the number of edges. Also, the overall time complexity is O(V2), if we use the adjacency matrix to represent a graph.

4. Shortest Path Tree

In the shortest path tree problem, we start with a source node s.

For any other node v in graph G, the shortest path between s and v is a path such that the total weight of the edges along this path is minimized. Therefore, the objective of the shortest path tree problem is to find a spanning tree such that the path from the source node s to any other node v is the shortest one in G.

We can solve this problem with Dijkstra’s algorithm:

Rendered by QuickLaTeX.com

Dijkstra’s algorithm has a similar structure to Prim’s algorithm. However, they have different selection criteria.

In Prim’s algorithm, we select the node that has the smallest weight. However, in Dijkstra’s algorithm, we select the node that has the shortest path weight from the source node. Therefore, the resulting spanning tree can be different for the same graph.

Let’s visually run Dijkstra’s algorithm for source node number 0 on our sample graph step-by-step:

The shortest path between node 0 and node 3 is along the path 0->1->3. However, the edge between node 1 and node 3 is not in the minimum spanning tree. Therefore, the generated shortest-path tree is different from the minimum spanning tree.

Similar to Prim’s algorithm, the time complexity also depends on the data structures used for the graph. The overall time complexity is O(V2) if we use the adjacency matrix to represent a graph. Also, if we use the adjacency list to represent a graph and store the edges in a priority queue, the overall time complexity is O(E log V).

5. Conclusion

In this tutorial, we discussed two similar problems: Minimum Spanning Tree and Shortest-Path Tree. Also, we compared the difference between Prim’s and Dijkstra’s algorithms.

Detailed implementations are available in our articles about Prim’s and Dijkstra’s algorithms, respectively.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments