Design Graph With Shortest Path Calculator

1import heapq
2
3class Graph:
4    def __init__(self, n, edges):
5        self.n = n
6        self.adj = [[] for _ in range(n)]
7        for u, v, cost in edges:
8            self.adj[u].append((v, cost))
9
10    def addEdge(self, edge):
11        u, v, cost = edge
12        self.adj[u].append((v, cost))
13
14    def shortestPath(self, node1, node2):
15        dist = [float('inf')] * self.n
16        dist[node1] = 0
17        pq = [(0, node1)]
18
19        while pq:
20            curDist, u = heapq.heappop(pq)
21            if u == node2:
22                return curDist
23            if curDist > dist[u]:
24                continue
25            for v, cost in self.adj[u]:
26                if dist[u] + cost < dist[v]:
27                    dist[v] = dist[u] + cost
28                    heapq.heappush(pq, (dist[v], v))
29        return -1
30
31# Demonstration
32if __name__ == "__main__":
33    edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
34    graph = Graph(4, edges)
35    print(graph.shortestPath(3, 2))  # Output: 6
36    print(graph.shortestPath(0, 3))  # Output: -1
37    graph.addEdge([1, 3, 4])
38    print(graph.shortestPath(0, 3))  # Output: 6
39

1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5#define INF INT_MAX
6
7typedef struct {
8    int n;
9    int** dist;
10} Graph;
11
12Graph* createGraph(int n, int edges[][3], int edgesSize) {
13    Graph* graph = (Graph*)malloc(sizeof(Graph));
14    graph->n = n;
15    graph->dist = (int**)malloc(n * sizeof(int*));
16    for (int i = 0; i < n; i++) {
17        graph->dist[i] = (int*)malloc(n * sizeof(int));
18        for (int j = 0; j < n; j++)
19            graph->dist[i][j] = (i == j) ? 0 : INF;
20    }
21    for (int i = 0; i < edgesSize; i++) {
22        int u = edges[i][0];
23        int v = edges[i][1];
24        graph->dist[u][v] = edges[i][2];
25    }
26    for (int k = 0; k < n; k++) {
27        for (int i = 0; i < n; i++) {
28            for (int j = 0; j < n; j++) {
29                if (graph->dist[i][k] != INF && graph->dist[k][j] != INF)
30                    graph->dist[i][j] = (graph->dist[i][j] > graph->dist[i][k] + graph->dist[k][j]) ? graph->dist[i][k] + graph->dist[k][j] : graph->dist[i][j];
31            }
32        }
33    }
34    
35    return graph;
36}
37
38void addEdge(Graph* graph, int u, int v, int cost) {
39    graph->dist[u][v] = cost;
40    // Re-run Floyd-Warshall
41    for (int k = 0; k < graph->n; k++) {
42        for (int i = 0; i < graph->n; i++) {
43            for (int j = 0; j < graph->n; j++) {
44                if (graph->dist[i][k] != INF && graph->dist[k][j] != INF)
45                    graph->dist[i][j] = (graph->dist[i][j] > graph->dist[i][k] + graph->dist[k][j]) ? graph->dist[i][k] + graph->dist[k][j] : graph->dist[i][j];
46            }
47        }
48    }
49}
50
51int shortestPath(Graph* graph, int node1, int node2) {
52    if(graph->dist[node1][node2] == INF)
53        return -1;
54    return graph->dist[node1][node2];
55}
56
57int main() {
58    int edges[4][3] = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
59    Graph* graph = createGraph(4, edges, 4);
60    printf("%d\n", shortestPath(graph, 3, 2)); // Output: 6
61    printf("%d\n", shortestPath(graph, 0, 3)); // Output: -1
62    addEdge(graph, 1, 3, 4);
63    printf("%d\n", shortestPath(graph, 0, 3)); // Output: 6
64    
65    // Free the memory
66    for(int i = 0; i < graph->n; i++)
67        free(graph->dist[i]);
68    free(graph->dist);
69    free(graph);
70    return 0;
71}