Dijkstra vs. Kruskal

Key takeaways:
Dijkstra’s algorithm finds the shortest path in a weighted graph from a source vertex to all others.
Kruskal’s algorithm identifies the minimum spanning tree in a weighted graph.
Dijkstra uses a priority queue to iteratively calculate the shortest paths to all vertices.
Kruskal uses union-find to ensure no cycles form while constructing the minimum spanning tree.
Dijkstra is focused on individual shortest paths, while Kruskal emphasizes minimum connection cost for all nodes.
Both algorithms have distinct use cases but operate on weighted graphs.

Dijkstra’s algorithm is used to find the shortest path in a weighted graph, while Kruskal’s algorithm is applied to find the minimum spanning tree of a weighted graph, each serving distinct purposes in graph theory.

Dijkstra’s algorithm

Dijkstra’s algorithm is designed to find the shortest path between a starting node and all other nodes in a weighted graph. It is a single-source shortest-path algorithm, meaning it computes the shortest path from one source node to every other node in the graph.

How it works?

Initialization: Start by assigning a tentative distance value to each node. The initial distance to the source node is 0, and the distances to all other nodes are set to infinity.
Exploration: Visit the node with the smallest tentative distance and explore its neighbors. For each neighbor, calculate the tentative distance through the current node. If this new distance is smaller than the current distance, update the distance.
Iteration: Mark the current node as visited (i.e., its shortest path is found), and repeat the process for the remaining unvisited nodes until all nodes have been visited.

Key features

Greedy algorithm: Dijkstra’s algorithm uses a greedy approach, always selecting the next node with the smallest tentative distance.
Time complexity: The time complexity of Dijkstra’s algorithm is $O(E+VlogV)$ with a priority queue (using a binary heap), where E is the number of edges and V is the number of vertices.
Applications: Dijkstra’s algorithm is widely used in routing and navigation systems, such as GPS software, to find the fastest route between two locations. It is also used in network routing protocols and other scenarios where the shortest path is critical.

Coding example

Here’s the coding example of Dijkstra algorithm:

import heapq

def dijkstra(graph, source):

    distances = {node: float('infinity') for node in graph}
    distances[source] = 0
    priority_queue = [(0, source)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for adjacent, weight in graph[current_node].items():
            new_distance = current_distance + weight

            if new_distance < distances[adjacent]:
                distances[adjacent] = new_distance
                heapq.heappush(priority_queue, (new_distance, adjacent))

    return distances

# Example usage
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(shortest_distances)

Code explanation

Line 1: We import the heapq module for the priority queue implementation.
Line 3: We define a function, dijkstra, that takes a graph and a starting node as input.
Line 5: We initialize a distances dictionary to store tentative distances from the start to each node. This is initially set to infinity.
Line 6: We set the distance from the start to itself as 0 and initialize the priority queue with the starting node and distance 0.
Line 9: We add a while loop that runs till the priority queue is not empty.
Line 10: Inside the loop, we pop the node with the smallest tentative distance from the priority queue.
Lines 12–13: We check if the current path is shorter than the stored distance. If yes, we continue to the next iteration.
Lines 15–20: We add a for loop to update the distances for neighbors and use an if condition to push the distance into the priority queue if a shorter path is found.
Line 22: We return the updated distances dictionary that contains the shortest paths from our target node.
Lines 25–30: We create a sample graph with four nodes to test the implementation of the dijkstra function created.
Line 32: We choose a starting node to calculate the shortest distances.
Line 33: We call the dijkstra function and pass our sample graph and starting node to the function. The shortest distances returned by the function are stored in the variable shortest_distances.

Kruskal’s algorithm

Kruskal’s algorithm is used to find a minimum spanning tree (MST) of a connected, weighted graph. A minimum spanning tree is a subset of the graph’s edges that connects all the vertices together without cycles and with the minimum possible total edge weight.

How it works?

Sort edges: Begin by sorting all the edges of the graph in increasing order of their weight.
Edge selection: Starting from the smallest edge, add it to the spanning tree if it doesn’t form a cycle. This is done by checking if the two vertices of the edge are already connected in the tree (using a union-find data structure).
Repeat: Continue adding edges until $V−1$ edges have been added to the tree (where V is the number of vertices in the graph).

Key features

Greedy algorithm: Like Dijkstra’s, Kruskal’s algorithm is greedy. It selects the smallest edge at each step, ensuring the minimal total weight for the spanning tree.
Time complexity: The time complexity of Kruskal’s algorithm is $O(ElogE)$ due to the edge sorting step, where $E$ is the number of edges. If union-find operations are used efficiently, the complexity can be reduced to $O(Eα(V))$ , where $α(V)$ is the inverse Ackermann function, which grows extremely slowly.
Applications: Kruskal’s algorithm is used in network design, such as in the creation of minimum-cost spanning networks, where we aim to connect a set of points (nodes) with the minimum total cost.

Coding example

Here’s the coding example of Kruskal’s algorithm:

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.edges = []

    def add_edge(self, src, dest, weight):
        self.edges.append([src, dest, weight])

    def find_set(self, parent, node):
        if parent[node] == node:
            return node
        return self.find_set(parent, parent[node])

    def union_sets(self, parent, rank, set1, set2):
        root1 = self.find_set(parent, set1)
        root2 = self.find_set(parent, set2)

        if rank[root1] < rank[root2]:
            parent[root1] = root2
        elif rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root2] = root1
            rank[root1] += 1

    def kruskal(self):
        mst = []
        self.edges = sorted(self.edges, key=lambda item: item[2])

        parent = []
        rank = []

        for vertex in range(self.vertices):
            parent.append(vertex)
            rank.append(0)

        edge_index = 0
        while len(mst) < self.vertices - 1:
            src, dest, weight = self.edges[edge_index]
            edge_index += 1
            set1 = self.find_set(parent, src)
            set2 = self.find_set(parent, dest)

            if set1 != set2:
                mst.append([src, dest, weight])
                self.union_sets(parent, rank, set1, set2)

        return mst


# Example usage:
graph = Graph(4)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 2, 6)
graph.add_edge(0, 3, 5)
graph.add_edge(1, 3, 15)
graph.add_edge(2, 3, 4)

minimum_spanning_tree = graph.kruskal()
print("Minimum Spanning Tree:", minimum_spanning_tree)

Code explanation

Lines 1–4: We defined a class called Graph to represent an undirected graph. It has an __init__ method that initializes the graph with a given number of vertices and an empty list to store the edges.
Lines 6–7: We use the add_edge method to add an edge to the graph. It takes three parameters: the two vertices and the weight of the edge. The edge information is stored as a list [src, dest, weight] and added to the self.edges list.
Lines 9–12: The find_set method is a helper function for the union-find algorithm. It is used to find the set to which a particular element belongs.
Lines 14–24: The union_sets method is another helper function for the union-find algorithm. It performs the union operation of two sets represented by x and y.
Lines 26–35: The kruskal method is the main implementation of Kruskal’s algorithm. It initializes an empty list mst to store the minimum spanning tree and sorts the edges of the graph based on their weights.
Lines 37–46: The algorithm iterates through the sorted edges, adding them to the result if including the edge does not form a cycle in the minimum spanning tree. The union operation is used to merge the sets of the vertices set1 and set2.
Line 48: Finally, the kruskal method returns the minimum spanning tree represented as a list of edges.
Lines 52–60: The example usage at the end creates a Graph object, adds edges with weights, and prints the minimum spanning tree obtained using Kruskal’s algorithm.

Dijkstra vs. Kruskal: Key Differences

	Dijkstra	Kruskal
Purpose	Finds the shortest path between a source node and all other nodes in a weighted graph.	Finds the minimum spanning tree (MST) of a weighted graph.
Type of problem	Single-source shortest path problem (SSSP).	Minimum spanning tree problem (MST).
Graph type	Typically used on graphs that may or may not be connected, and it requires a starting node.	Used on connected graphs, where the goal is to connect all nodes in the minimum-cost tree.
Algorithm design	Works by exploring nodes in a greedy manner, always expanding the node with the smallest tentative distance.	Works by sorting edges and greedily adding the smallest edge that does not form a cycle in the tree.
Edge relaxation	Uses edge relaxation to update the shortest known distance to each node.	Uses a union-find (disjoint-set) data structure to ensure no cycles are formed while adding edges to the MST.
Time complexity	$O(E+V log V)$ with a priority queue.	$O(E log E)$ due to the edge sorting step.

When to use Dijkstra and Kruskal

Dijkstra’s algorithm is preferred when:
- You need to find the shortest path from a source node to all other nodes.
- You are working with a graph where edge weights are non-negative.
- You are solving routing problems like GPS navigation.
Kruskal’s algorithm is preferred when:
- You need to find the minimum spanning tree (MST) of a graph.
- You are working with a graph that can be sparse (few edges).
- You are designing networks or solving problems that require a minimal cost to connect all points.

Conclusion

Dijkstra’s and Kruskal’s algorithms are two essential graph algorithms, each serving a different purpose. Dijkstra’s algorithm is perfect for finding the shortest path in a graph, while Kruskal’s algorithm is ideal for constructing a minimum spanning tree. Understanding the differences between these algorithms is vital for selecting the right tool for your specific problem. Whether you’re working on network routing, optimization problems, or network design, these algorithms provide efficient and scalable solutions to fundamental graph problems.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

Which is better, Kruskal or Dijkstra?

Kruskal and Dijkstra’s algorithms serve different purposes: Kruskal is better for finding the minimum spanning tree (MST) in a graph, while Dijkstra is better for finding the shortest path from a single source to all other nodes. The choice depends on the problem you’re solving.

Which algorithm is better than Dijkstra?

The A* algorithm is often considered better than Dijkstra’s for pathfinding, as it uses heuristics to find the shortest path more efficiently by guiding the search towards the target.

What is Dijkstra best used for?

Dijkstra’s algorithm is best used for finding the shortest path between a starting node and all other nodes in a weighted graph.

Free Resources