Home/Blog/Interview Prep/Understanding weighted graph algorithms

Understanding weighted graph algorithms

13 min read

Mar 19, 2025

content

Weighted graph algorithms: Applications

Types of weighted graph algorithms

Shortest path algorithms

Dijkstra’s algorithm

Bellman-Ford algorithm

Floyd-Warshall algorithm

Minimum spanning tree (MST) algorithms

Kruskal’s algorithm

Prim’s algorithm

Network flow algorithms

Ford-Fulkerson algorithm

Edmonds-Karp algorithm

Time and space complexity

What’s next?

Graphs are important, especially if you seek a job at top tech companies like MAANG (Meta, Amazon, Apple, Netflix, and Google). Graph problems are common in coding interviews because they test your problem-solving skills in real-world scenarios. Whether you’re finding the shortest path, figuring out how to network systems efficiently, or even analyzing social media trends, graph algorithms are the backbone of these tasks. Graph algorithms can be broadly classified into weighted and unweighted graphs.

Mastering Graph Algorithms

Mastering Graph Algorithms

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer. You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings. The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.

15hrs

Beginner

32 Playgrounds

25 Quizzes

This blog will explore weighted graph algorithms and their practical applications, such as finding the shortest path or building low-cost networks. We will also examine the steps and code examples for each algorithm.

We will also provide resources to help you prepare for coding interviews where these concepts often appear.

We will discuss the following weighted graph algorithms:

Dijkstra’s algorithm: Finds the shortest path from a starting node to all other nodes in a graph with non-negative weights.
Bellman-Ford algorithm: Solves the single-source shortest path problem, handling graphs with negative weights.
Floyd-Warshall algorithm: Computes shortest paths between all pairs of nodes in a graph.
Prim’s algorithm: Builds a minimum spanning tree (MST) by starting from an arbitrary node and growing the tree by adding the smallest edge.
Kruskal’s algorithm: Constructs an MST by adding edges in order of increasing weight, ensuring no cycles are formed.
Ford-Fulkerson algorithm: Finds the maximum flow in a flow network through paths until no more capacity is available.
Edmonds-Karp algorithm: An implementation of Ford-Fulkerson that uses BFS to find maximum flow in a flow network, improving performance for large networks.

Weighted graph algorithms: Applications#

As we discussed before, weighted graph algorithms have many real-world applications. They are important for solving various computational problems across multiple domains. The table below highlights some key problems that different weighted graph algorithms solve and briefly describes each.

Weighted Graph Algorithm	Key Problem	Real-World Application
Dijkstra’s algorithm	The shortest path in weighted graphs	Finding the shortest route in a navigation system (e.g., Google Maps) from one city to another.
Bellman-Ford algorithm	The shortest path with negative weights	Routing in computer networks where distances might include negative weights, like internet packet delivery.
Floyd-Warshall algorithm	All-pairs shortest path	Determining the shortest distances between all pairs of airports in an airline network.
Kruskal’s algorithm	Minimum spanning tree (MST)	Building an electrical grid connecting cities with minimum cost.
Prim’s algorithm	Minimum spanning tree (MST)	Creating a communication network that connects various company offices with the least amount of cabling.
Ford-Fulkerson algorithm	Maximum flow in flow networks	Maximizing the water flow through a system of interconnected pipes.
Edmonds-Karp algorithm	Maximum flow in flow networks	Optimizing the distribution of goods in a supply chain.

Let’s explore these categories and the respective algorithms related to them:

Shortest path algorithms#

Shortest path algorithms help find the shortest route between two nodes in a graph. Algorithms like Dijkstra’s or Bellman-Ford look for the shortest way to connect two nodes by minimizing the total weight of a path joining them. Let’s discuss these algorithms in the detail below:

Dijkstra’s algorithm
Bellman-Ford algorithm
Floyd-Warshall algorithm

Dijkstra’s algorithm#

Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph. The algorithm uses a greedy strategy, starting from a source node and exploring all its neighbors, updating the shortest known distances to these neighbors.

Let’s look at the step-by-step implementation of the algorithm:

Initialize the distances for all nodes to infinity, except for the source node, which is initialized to zero. Use a priority queue to store tuples, each containing a node and its distance from the source node, and a dictionary to keep track of the shortest distances from the source to each node.
Remove the node with the smallest distance from the priority queue. To check if a shorter path passes through the removed node to any of its neighbors, compute the length of each such path. This can be done by adding the distance to the removed node and the weight of the edge connecting it to each neighbor.
If the neighbor’s new distance is less than its previously recorded distance from the source, update it and add the neighbor and its updated distance back into the priority queue.
Continue this process until all nodes have been removed from the priority queue.
Finally, return the dictionary containing the shortest distances for all nodes after complete processing.

Let’s look at the following illustration to get a better understanding of the solution:

import heapq
def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances
def main():
  graph = {
      'A': [('B', 4), ('C', 2), ('D', 5)],
      'B': [('A', 4), ('D', 1), ('F', 3)],
      'C': [('A', 2), ('D', 8)],
      'D': [('A', 5), ('B', 1), ('C', 8)],
      'E': [('F', 7)],
      'F': [('B', 3), ('E', 7)]
  }
  
  for key in graph.keys():
    print("Source: ", key)
    print("Dijkstra's Algorithm: ", dijkstra(graph, key))
    print("-"*100)
if __name__ == "__main__":
    main()

Bellman-Ford algorithm#

The Bellman-Ford algorithm determines the shortest path from a single source node to every other node in a weighted graph.

Unlike Dijkstra’s algorithm, Bellman-Ford can work with graphs with edges with negative weights. However, it is important to distinguish between handling negative weights and detecting negative weight cycles. The presence of edges with negative weights does not necessarily imply a negative weight cycle.

Let’s look at a scenario involving negative weight cycles. Imagine figuring out the shortest path to all destinations from your home. You consider all possible roads (edges), updating your understanding of how far each place is from your home. You repeat this process, optimizing distances as much as possible. Suppose you still find shorter paths after a significant number of passes. In that case, it indicates the presence of a negative weight cycle, where traversing such a cycle continuously reduces the total distance with every iteration. This scenario highlights why shortest paths can’t be found in negative weight cycles. The Bellman-Ford algorithm can detect the presence of such cycles.

Let’s look at the step-by-step implementation of the algorithm:

Use a dictionary to store the shortest distances of all nodes from the source. The shortest path from a node to itself is always $0$ . This reflects that no cost or distance is required to reach the start node from itself, whereas the shortest paths to all other nodes are unknown initially. Representing these distances as infinity indicates that these nodes are unreachable from the start node at the beginning of the algorithm.
Iterate through the graph and for each node:
- For each edge in the graph, check if a shorter path to the target node of the edge can be found by passing through the source node of the edge. If a shorter path is found, update the distance for the target node in the dictionary. Otherwise, continue to the next edge.
- Repeat this process $N–1$ time, where $N$ is the number of nodes. The reason for $N-1$ iterations is that the shortest path in a graph can have at most $N-1$ edges.
The graph contains a negative weight cycle if any distance is updated after one more iteration is performed.

Let’s look at the following illustration to get a better understanding of the solution:

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node]:
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
    for node in graph:
        for neighbor, weight in graph[node]:
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("Graph contains a negative-weight cycle")
    return distances
def main():
  graph = {
      'A': [('B', 4), ('C', 2), ('D', 5)],
      'B': [('A', 4), ('D', 1), ('F', 3)],
      'C': [('A', 2), ('D', 8)],
      'D': [('A', 5), ('B', 1), ('C', 8)],
      'E': [('F', 7)],
      'F': [('B', 3), ('E', 7)]
  }
  
  for key in graph.keys():
    print("Shortest path from source:",key,"using Bellman-Ford Algorithm: ", bellman_ford(graph, key))
    print("-"*100)
if __name__ == "__main__":
    main()

Floyd-Warshall algorithm#

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes in a graph. Unlike single-source algorithms, such as Dijkstra’s algorithm, which focuses on finding the shortest paths from a single source to all destinations, Floyd-Warshall computes the shortest paths for every possible pair.

Let’s look at the step-by-step implementation of the algorithm:

Initialize the distances between every pair of nodes using a matrix where any index $(i, j)$ represents the shortest distance between node $i$ and node $j$ .
The distance is set to infinity (or a very large number) if there’s no direct edge and 0 if $i == j$ .
Check if going through node $k$ results in a shorter path between $i$ and $j$ than the currently known distance and update the index $(i, j)$ with this new shorter path.

The main concept is that if the route from node i to node j via node k is shorter than the previously known route from i to j, we should update the distance with this shorter route.

Let’s look at the following illustration to get a better understanding of the solution:

def floyd_warshall(graph):
    nodes = list(graph.keys())
    dist = {node: {other: float('inf') for other in nodes} for node in nodes}
    for node in nodes:
        dist[node][node] = 0
    for node in graph:
        for neighbor, weight in graph[node]:
            dist[node][neighbor] = weight
    for k in nodes:
        for i in nodes:
            for j in nodes:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
def main():
    graph = {
        'A': [('B', 3), ('C', 10)],
        'B': [('D', 1)],
        'C': [('F', 2)],
        'D': [('C', 8)],
        'E': [('F', 7)],
        'F': [('B', 6)]
    }
    for key in graph.keys():
        result = floyd_warshall(graph)
        print("Shortes path from source:", key, "using Floyd-Warshall's algorithm: \n", )
        print(result.get(key))
        print("-" * 100)
if __name__ == "__main__":
    main()

Let’s discuss these algorithms in the detail below:

Kruskal’s algorithm#

Kruskal’s algorithm finds the MST in a weighted, undirected graph. It connects all the nodes with the smallest possible total edge weight, ensuring no cycles are formed.

Let’s look at the step-by-step implementation of the algorithm:

Use the UnionFind class to manage the connected components of the graph. It uses two main operations:
- The find function returns the node’s root, using path compression to flatten the tree.
- The union function connects two components by linking their roots. It uses rank to keep the tree shallow.
Sort the edges by weight and in that order for each edge; if the nodes connected by that edge are in different sets, call the union function on the nodes to merge the two sets.
Once all the sets have merged into one, the edges in that set form a connected graph without cycles—the minimum spanning tree.

Let’s look at the code for the algorithm we just discussed:

class UnionFind:
    def __init__(self, nodes):
        self.parent = {node: node for node in nodes}
        self.rank = {node: 0 for node in nodes}
    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1
def kruskal(graph):
    edges = []
    
    for node in graph:
        for neighbor, weight in graph[node]:
            edges.append((weight, node, neighbor))
    
    edges.sort()
    uf = UnionFind(graph.keys())
    mst = []
    for weight, node1, node2 in edges:
        if uf.find(node1) != uf.find(node2):
            uf.union(node1, node2)
            mst.append((node1, node2, weight))
    return mst
def main():
  graph = {
      'A': [('B', 4), ('C', 2), ('D', 5)],
      'B': [('A', 4), ('D', 1), ('F', 3)],
      'C': [('A', 2), ('D', 8)],
      'D': [('A', 5), ('B', 1), ('C', 8)],
      'E': [('F', 7)],
      'F': [('B', 3), ('E', 7)]
  }
  
  print("Minimum spanning tree using Kruskal's algorithm", kruskal(graph))
if __name__ == "__main__":
    main()

Prim’s algorithm#

Prim’s algorithm finds a graph’s minimum spanning tree. It builds the MST incrementally, adding one node at a time by selecting the smallest edge that links a node already in the MST to a node not yet included.

Let’s look at the step-by-step implementation of the algorithm:

Mark the starting node as visited to indicate it is in the minimum spanning tree.
Insert all edges connected to the starting node into a priority queue (min heap), where each edge is stored with its weight.
Select the edge with the smallest weight that links a visited node to an unvisited node. If it hasn’t been added yet, Add it to the minimum spanning tree.
For each edge that’s added, mark its unvisited node as visited. Then for each unvisited neighbor of this node, add the edge connecting them to the heap.
The minimum spanning tree is complete once all vertices are included in the spanning tree.

Let’s look at the code for the algorithm we just discussed:

import heapq
def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    while edges:
        weight, node1, node2 = heapq.heappop(edges)
        if node2 not in visited:
            visited.add(node2)
            mst.append((node1, node2, weight))
            for neighbor, weight in graph[node2]:
                if neighbor not in visited:
                    heapq.heappush(edges, (weight, node2, neighbor))
    return mst
def main():
  graph = {
      'A': [('B', 4), ('C', 2), ('D', 5)],
      'B': [('A', 4), ('D', 1), ('F', 3)],
      'C': [('A', 2), ('D', 8)],
      'D': [('A', 5), ('B', 1), ('C', 8)],
      'E': [('F', 7)],
      'F': [('B', 3), ('E', 7)]
  }
  
  print("Source: ", 'A')
  print("Minimum spanning tree using Prim's algorithm: ", prim(graph, 'A'))
if __name__ == "__main__":
    main()

The following article summarizes the differences between Kruskal and Prim algorithms.

Network flow algorithms#

Network flow helps to understand how much of something (like water, data, or goods) can flow through a network from one point to another. The algorithms calculating the maximum amount that can flow through the network without exceeding the pipe capacities are as follows:

Ford-Fulkerson algorithm
Edmonds-Karp algorithm

Let’s discuss these algorithms in the detail below:

Ford-Fulkerson algorithm#

The Ford-Fulkerson algorithm finds the maximum possible flow in a flow network from a source to a sink. Think of it as a system of pipes where you want to push as much water as possible from one point to another through various connected pipes. Each pipe has a limit (capacity) on how much water can pass through it. The goal is to find the best way to push water through the network without exceeding the capacity of any pipe.

Note: Ford-Fulkerson offers flexibility in finding paths, allowing for techniques like depth-first search (DFS) or breadth-first search (BFS).

Let’s look at the step-by-step implementation of the algorithm:

Create an empty parent dictionary to keep track of paths from the source to sink and initialize the total flow variable to 0.
Use breadth-first search (BFS) at each step to check if there is a path from the source to the sink where the flow can still increase.
For every edge along the path, add an edge with capacity 0 that’s directed opposite (from its head to tail) if it doesn’t already exist.

Note: The capacity of each new edge indicates how much the flow in the original edge can be reduced.

Find out how much flow can be pushed along this path by looking for the edge with the smallest capacity (called the residual capacity). Increase the flow along the path by adjusting the capacities of its edges, as described next.
Decrease the capacity of each edge in the path by the residual capacity and increase the capacity of the corresponding reverse edge by the same amount. This adjustment allows the flow in the original edge to be “pushed back” in future iterations if needed.
Add the residual capacity to the total flow variable to update the network’s flow.
The max flow is computed once no more paths can be found.

Let’s look at the following illustration to get a better understanding of the solution:

from collections import deque, defaultdict
def bfs(graph, source, sink, parent):
    visited = set()
    queue = deque([source])
    visited.add(source)
    while queue:
        u = queue.popleft()
        for v, capacity in graph[u].items():
            if v not in visited and capacity > 0:
                queue.append(v)
                visited.add(v)
                parent[v] = u
                if v == sink:
                    return True
    return False
def ford_fulkerson(graph, source, sink):
    parent = {}
    max_flow = 0
    while bfs(graph, source, sink, parent):
        path_flow = float("Inf")
        s = sink
        
        while s != source:
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            if v not in graph:
                graph[v] = {}
            if u not in graph[v]: 
                graph[v][u] = 0
            graph[v][u] += path_flow
            v = parent[v]
    return max_flow
def main():
  graph = {
    0: {1: 16, 2: 13},
    1: {3: 12},
    2: {1: 4, 5: 7},
    3: {5: 20},
    4: {5: 4},
    5: {}
  }
    
  source = 0
  sink = 5
  
  print("Source: ", source)
  print("Sink: ", sink)
  print("Maximum Flow using Ford-Fulkerson algorithm: ", ford_fulkerson(graph, source, sink))
if __name__ == "__main__":
    main()

Ford-Fulkerson works by finding paths in any order, making it dependent on the flow values and potentially inefficient for large graphs.

Edmonds-Karp algorithm#

The Ford-Fulkerson and Edmonds-Karp algorithms are designed to tackle the maximum flow problem in flow networks. They share a common approach: both algorithms continuously identify paths from the source to the sink and increase the flow along those paths until no more viable paths are available.

The primary difference between the two lies in how they discover these paths. Edmonds-Karp specifically employs BFS to locate paths, ensuring that each identified path is the shortest regarding the number of edges. This adjustment allows Edmonds-Karp to operate in polynomial time, while the performance of Ford-Fulkerson can be unpredictable and sometimes non-polynomial, influenced by the chosen search algorithm.

Note: For hands-on practice, a free interview prep road map, and interview preparation tips, check out all of Educative ’s Interview Prep resources.

Time and space complexity#

When working with weighted graph algorithms, it’s important to understand their time and space complexities. These metrics help us estimate the efficiency of algorithms and determine their suitability for different types of problems. The table below compares the time and space complexities for the graph algorithms discussed above:

Here:

V = Number of nodes in the graph
E = Number of edges in the graph

What’s next?#

Weighted graph algorithms play a crucial role in coding interviews, particularly for positions that require strong problem-solving skills in data structures and algorithms. If you’re preparing for coding interviews, Educative offers in-depth courses and learning paths covering graph algorithms and other essential topics for all skill levels. It provides the resources to master everything from basic graph traversal to advanced algorithms, giving you the edge to excel in interviews and advance your tech career. Explore our top resources to prepare effectively. These resources include Grokking the Coding Interview Patterns in Python and Data Structures for Coding Interviews in C++. These courses are also available in other languages, as can be seen below:

Frequently Asked Questions

Which weighted graph algorithms are commonly asked in coding interviews, especially for MAANG companies?

In coding interviews, you’ll likely encounter algorithms like Dijkstra’s for shortest paths, Prim’s and Kruskal’s for minimum spanning trees, and Ford-Fulkerson or Edmonds-Karp for network flow problems.

What is the difference between Dijkstra’s algorithm and Bellman-Ford?

Dijkstra’s algorithm is faster but only works with non-negative edge weights, while Bellman-Ford can handle graphs with negative edge weights, although it’s slower.

When should I use Prim’s algorithm vs. Kruskal’s algorithm for finding an MST?

Prim’s algorithm is used when the graph is dense (with many edges) because it adds one edge from a starting node at a time. Kruskal’s algorithm works better for sparse graphs, as it processes edges in increasing order of weight.

What is the advantage of Floyd-Warshall over Dijkstra’s algorithm?

Floyd-Warshall finds the shortest paths between all pairs of nodes in the graph, while Dijkstra focuses on the shortest path from a single source node to all other nodes.

How does Edmonds-Karp improve the Ford-Fulkerson algorithm?

Edmonds-Karp is an implementation of Ford-Fulkerson that uses BFS to find augmenting paths. It ensures that the shortest available paths are explored first, which improves performance in larger networks.

Written By:

Hassan Shahzad

Join 2.5 million developers at

Explore the catalog

Free Resources

Weighted Graph Algorithm	Time Complexity	Space Complexity
Dijkstra’s algorithm	O((V + E) log V)	O(V+E)
Bellman-Ford algorithm	O(VE)	O(V)
Floyd-Warshall algorithm	O(V³)	O(V²)
Kruskal’s algorithm	O(E logE)	O(V+E)
Prim’s algorithm	O((VE) log V)	O(V+E)
Ford-Fulkerson algorithm with BFS (Edmonds-Karp)	O(VE²)	O(V)

Understanding weighted graph algorithms

Weighted graph algorithms: Applications#

Types of weighted graph algorithms#

Shortest path algorithms#

Dijkstra’s algorithm#

Bellman-Ford algorithm#

Floyd-Warshall algorithm#

Minimum spanning tree (MST) algorithms#

Kruskal’s algorithm#

Prim’s algorithm#

Network flow algorithms#

Ford-Fulkerson algorithm#

Edmonds-Karp algorithm#

Time and space complexity#

What’s next?#

Frequently Asked Questions

Which weighted graph algorithms are commonly asked in coding interviews, especially for MAANG companies?

What is the difference between Dijkstra’s algorithm and Bellman-Ford?

When should I use Prim’s algorithm vs. Kruskal’s algorithm for finding an MST?

What is the advantage of Floyd-Warshall over Dijkstra’s algorithm?

How does Edmonds-Karp improve the Ford-Fulkerson algorithm?

Type	Algorithms
Shortest path algorithms	Dijkstra’s algorithm Bellman-Ford algorithm Floyd-Warshall algorithm
Minimum spanning tree algorithms	Prim’s algorithm Kruskal’s algorithm
Network flow algorithms	Ford-Fulkerson algorithm Edmonds-Karp algorithm