Design Graph With Shortest Path Calculator

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

1class Graph:
2    def __init__(self, n, edges):
3        self.n = n
4        self.dist = [[float('inf')] * n for _ in range(n)]
5        for i in range(n):
6            self.dist[i][i] = 0
7        for u, v, cost in edges:
8            self.dist[u][v] = cost
9        self.floyd_warshall()
10
11    def floyd_warshall(self):
12        for k in range(self.n):
13            for i in range(self.n):
14                for j in range(self.n):
15                    if self.dist[i][k] != float('inf') and self.dist[k][j] != float('inf'):
16                        self.dist[i][j] = min(self.dist[i][j], self.dist[i][k] + self.dist[k][j])
17
18    def addEdge(self, edge):
19        u, v, cost = edge
20        self.dist[u][v] = cost
21        self.floyd_warshall()
22
23    def shortestPath(self, node1, node2):
24        return -1 if self.dist[node1][node2] == float('inf') else self.dist[node1][node2]
25
26# Demonstration
27if __name__ == "__main__":
28    edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
29    graph = Graph(4, edges)
30    print(graph.shortestPath(3, 2))  # Output: 6
31    print(graph.shortestPath(0, 3))  # Output: -1
32    graph.addEdge([1, 3, 4])
33    print(graph.shortestPath(0, 3))  # Output: 6
34