2642. Design Graph With Shortest Path Calculator

Problem Description

In this problem, we are tasked with implementing a class, [Graph](/problems/graph_intro), that represents a directed weighted graph. A graph is composed of nodes (or vertices) connected by edges, each with an associated cost. The Graph class is supposed to support the following functionalities:

• Initialization with a specific number of nodes and a list of edges, where each edge is a triplet [from, to, edgeCost] representing an edge from node from to node to with a cost edgeCost.

• Adding a new edge to the graph which did not previously exist between two nodes.

• Finding the shortest path between any two nodes, which is the path where the sum of the costs of its constituent edges is the lowest possible. If no such path exists, the method should return -1.

The challenge in this problem is efficiently implementing these functionalities, particularly the path-finding operation, which is central to many applications in network analysis, logistics, and more.

Intuition

The intuition behind the solution lies in implementing effective ways to manage and query the graph upon which we can apply a shortest path algorithm. To represent the graph internally, we use a two-dimensional matrix (self.g). This allows us to quickly access the cost of any edge given a starting and ending node, defaulting to 'infinity' (inf) where edges do not exist.

For the shortest path algorithm, we can use a variant of Dijkstra's algorithm, which is well-known for finding the shortest paths between nodes in a graph with non-negative edge weights. Here's the high-level approach:

1. Initialize a dist array, representing the shortest discovered distances from node1 to every other node, with infinite values except for the starting node (node1), which has a distance of zero.

2. Create a vis array to keep track of nodes whose shortest distance is finalized and will no longer change.

3. Repeat the following steps n times (where n is the number of nodes in the graph):

   a. Select the unvisited node with the current smallest known distance (t).

   b. Mark this node as visited.

   c. Update the dist values of adjacent nodes using the edge costs from the selected node if it results in a shorter path than what is currently known.

4. Once completed, the dist array contains the shortest known distances from node1 to all other nodes. Specifically, dist[node2] will give us the minimum cost of the path from node1 to node2. If this value is inf, it means no path exists, and we return -1.

With this approach, addEdge simply updates the edge matrix self.g with the new edge cost, whereas shortestPath performs Dijkstra's algorithm as described to return the shortest path cost between two given nodes.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the [Graph](/problems/graph_intro) class consists of several components, each handling a distinct aspect of the graph's functionality. Here's a detailed breakdown:

1. Initialization (__init__ method):

   • We initialize a 2D matrix self.g with size n * n, where n is the number of nodes. This matrix will hold the edge costs, initialized to 'infinity' (inf) to represent no direct edge between nodes. This value is symbolic for the absence of a path and ensures it doesn't interfere with the calculation of minimum costs.
   • For each edge in the input list edges, we populate self.g with the corresponding edge cost at the position [from_i][to_i], where from_i and to_i are the starting and ending nodes of the edge i with cost edgeCost_i.

2. Adding an Edge (addEdge method):

   • It's a straightforward update of the edge cost matrix self.g for the new edge specified by the edge parameter.
   • The new edge's starting node, ending node, and cost are extracted from the input edge list and used to update self.g.

3. Finding the Shortest Path (shortestPath method):

   • Initialize a list dist with values 'infinity' (inf) for tracking the shortest distance from node1 to all other nodes. We set dist[node1] to 0 since the distance from node1 to itself is zero.
   • Create a list vis that will track whether we have finalized the shortest distance to a node. Initially, all values are set to False.
   • We use a for-loop to iterate n times, where n is the number of nodes:
     • Within this loop, we select the node with the smallest dist value that hasn't been visited yet (t). This greedy choice leads us to pick the nearest unvisited node.
     • We mark this node t as visited by setting vis[t] to True.
     • We then relax the edges by iterating over all nodes (j) and checking if the path through t offers a shorter path. If it does, we update dist[j] with the new minimum cost.
   • Finally, we check if dist[node2] is still 'infinity' (inf) to determine if node1 and node2 are disconnected; if so, we return -1. Otherwise, we return dist[node2], which is the minimum cost of the path found from node1 to node2.

Each step of the shortestPath method follows the standard Dijkstra's algorithm pattern with a slight modification to adapt it to a dense graph representation (2D matrix). This approach ensures that we can find the shortest path efficiently, even in a graph where the edges are represented with a matrix instead of an adjacency list or other sparse representation.

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have a graph with 4 nodes (numbered 0 through 3) and the following directed edges:

• An edge from node 0 to node 1 with a cost of 3
• An edge from node 1 to node 2 with a cost of 4
• An edge from node 2 to node 3 with a cost of 2
• An edge from node 0 to node 3 with a cost of 10

We want to find the shortest path from node 0 to node 3.

Step 1: Initialization

We instantiate a Graph object with 4 nodes and an initial list of edges: [(0, 1, 3), (1, 2, 4), (2, 3, 2), (0, 3, 10)].

Step 2: Representation

After initialization, our graph's internal matrix self.g will look like this, where inf denotes no direct edge:

1   0  1    2    3
20  0  3  inf   10
31 inf  0    4  inf
42 inf inf   0    2
53 inf inf  inf    0

Step 3: Add a New Edge

Let's say we add a new edge from node 1 to node 3 with a cost of 5 using the addEdge method:

1   0  1    2    3
20  0  3  inf   10
31 inf  0    4    5
42 inf inf   0    2
53 inf inf  inf    0

Step 4: Finding the Shortest Path

Now, to find the shortest path from node 0 to node 3, we follow Dijkstra's algorithm:

• Initialize dist with inf and set dist[0] to 0.
• The vis array will keep track of visited nodes, starting all as False.

For each iteration:

1. Pick the smallest dist value from unvisited nodes. First, it's 0 itself, with a distance of 0.

2. Visit node 0, and update distances to its adjacent nodes. dist[1] becomes 3, and dist[3] becomes 10.

3. Next, pick node 1 since it has the smallest dist of 3. Visit and update its neighbors. Since 1 -> 3 is 5, the total cost 0 -> 1 -> 3 would be 3 + 5 = 8, which is less than the existing 10. So, dist[3] is updated to 8.

4. Repeat the process for nodes 2 and 3, but since 0 -> 1 -> 3 is already the smallest path to 3, there will be no more updates.

In the end, dist[3] equals 8, which is the shortest path cost from 0 to 3.

This would conclude our example, demonstrating how we would use the provided Graph class to add edges and find the shortest path between two nodes.

Solution Implementation

Time and Space Complexity

Time Complexity

• The constructor __init__ has a time complexity of O(n^2) because it initializes an n x n matrix, where each initialization operation has a constant time complexity, and we perform n * n such operations. Additionally, it iterates through each edge provided to fill in the graph, which adds an O(E) time complexity where E is the number of edges, leading to a total constructor complexity of O(n^2 + E).

• The addEdge function has a time complexity of O(1) as it performs a constant number of operations regardless of the graph size.

• For the shortestPath method, there is a nested loop structure. The outer loop runs n times, and for each iteration, the inner loops iterate up to n times to find the unvisited node with the smallest distance and to update the distances. This leads to an overall time complexity of O(n^2) for the shortest path calculation using Dijkstra's algorithm without a priority queue.

Space Complexity

• The space complexity of the class is O(n^2), mainly due to the adjacency matrix self.g which stores the weights of the edges between nodes.

• The shortestPath method uses an additional array dist of size n and a boolean array vis also of size n, which account for a space complexity of O(n). Since this does not dominate the O(n^2) space complexity of the class, the overall space complexity remains O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.