Design Graph With Shortest Path Calculator

Problem Statement

In this problem, we are working with a directed weighted graph characterized by a set of nodes and directed edges with associated costs. The nodes in the graph are labeled sequentially from 0 to n - 1. The graph's connections are defined by an array edges, where each element edges[i] = [fromi, toi, edgeCosti] represents a directed edge starting at node fromi and ending at node toi with a travel cost of edgeCosti.

We are required to implement a Graph class with specific functionalities:

• Initialization (Graph(int n, int[][] edges)): Constructs the graph using n nodes and the edges defined by the edges array.
• Adding an Edge (addEdge(int[] edge)): Incorporates a new directed edge into the graph. Here, edge is represented as [from, to, edgeCost], and it's guaranteed that such an edge did not previously exist between the specified nodes.
• Finding the Shortest Path (int shortestPath(int node1, int node2)): Determines the minimum cost path from node1 to node2. If such a path does not exist, the method returns -1.

The challenge involves accurately managing and querying the graph structure, especially under changing conditions as new edges are added.

Examples

Example 1

Input:

["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]

Output:

[null, 6, -1, null, 6]

Explanation:

Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.
g.shortestPath(0, 3); // return -1. There is no path from 0 to 3.
g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above.
g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

Constraints

• 1 <= n <= 100
• 0 <= edges.length <= n * (n - 1)
• edges[i].length == edge.length == 3
• 0 <= fromi, toi, from, to, node1, node2 <= n - 1
• 1 <= edgeCosti, edgeCost <= 106
• There are no repeated edges and no self-loops in the graph at any point.
• At most 100 calls will be made for addEdge.
• At most 100 calls will be made for shortestPath.

Approach and Intuition

From the example provided, let's break down the approach and methodology to address the tasks defined by the Graph class:

• Initialization:

  • The graph initializes with a specific number of nodes and all edges listed. This might involve setting up a data structure, typically an adjacency list or matrix, to efficiently store and retrieve the connections and their costs.

• Adding an Edge:

  • When a new edge is added, it must update the existing structure without violating the graph's properties (no self-loops and no repeated edges). This addition will affect future operations, particularly the path-finding queries.

• Finding the Shortest Path:

  • The key here is implementing an effective algorithm to find the shortest path. Considering the constraints (e.g., number of nodes up to 100, which is moderately small), algorithms like Dijkstra's, Bellman-Ford, or even Floyd-Warshall can be utilized for path finding in this context. Dijkstra’s algorithm is generally efficient for graphs with non-negative weights, which fits as all edgeCosts are positive.
  • If the method returns -1, it indicates no viable path exists from the start to the target node under current graph conditions.

Taking the example through these points:

1. Initialization: The graph is set up with the given edges which define direct paths between various nodes and their associated costs.
2. Query for Shortest Path: Before and after adding new edges, the shortest path costs are assessed.
3. Modification: Adding a new edge potentially creates new paths or reduces the cost of existing paths, further demonstrating the dynamic nature of path queries with graph modification.

This approach underlies the dynamics of mutable graph structures and emphasizes efficient graph manipulation and query techniques.

Solutions

class Network {
public:
    vector<vector<int>> distanceMatrix;
    Network(int size, vector<vector<int>>& connections) {
        distanceMatrix = vector<vector<int>>(size, vector<int>(size, 1e9));
        for (auto &connection : connections)
            distanceMatrix[connection[0]][connection[1]] = connection[2];
        for (int i = 0; i < size; ++i)
            distanceMatrix[i][i] = 0;
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                for (int k = 0; k < size; k++)
                    distanceMatrix[j][k] = min(distanceMatrix[j][k],
                                               distanceMatrix[j][i] + distanceMatrix[i][k]);
    }
        
    void connectEdges(vector<int> edgeInfo) {
        int size = distanceMatrix.size();
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                distanceMatrix[i][j] = min(distanceMatrix[i][j], 
                                           distanceMatrix[i][edgeInfo[0]] +
                                           distanceMatrix[edgeInfo[1]][j] +
                                           edgeInfo[2]);
    }
        
    int calculateShortestPath(int startPoint, int endPoint) {
        if (distanceMatrix[startPoint][endPoint] == 1e9) 
            return -1;
        return distanceMatrix[startPoint][endPoint];
    }
};