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}

1import java.util.*;
2
3class Graph {
4    private int n;
5    private int[][] dist;
6
7    public Graph(int n, int[][] edges) {
8        this.n = n;
9        dist = new int[n][n];
10        for (int[] row : dist)
11            Arrays.fill(row, Integer.MAX_VALUE);
12        for (int i = 0; i < n; i++)
13            dist[i][i] = 0;
14        for (int[] edge : edges) {
15            dist[edge[0]][edge[1]] = edge[2];
16        }
17        floydWarshall();
18    }
19
20    public void floydWarshall() {
21        for (int k = 0; k < n; k++) {
22            for (int i = 0; i < n; i++) {
23                for (int j = 0; j < n; j++) {
24                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE)
25                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
26                }
27            }
28        }
29    }
30
31    public void addEdge(int[] edge) {
32        dist[edge[0]][edge[1]] = edge[2];
33        floydWarshall();
34    }
35
36    public int shortestPath(int node1, int node2) {
37        return dist[node1][node2] == Integer.MAX_VALUE ? -1 : dist[node1][node2];
38    }
39
40    public static void main(String[] args) {
41        int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
42        Graph graph = new Graph(4, edges);
43        System.out.println(graph.shortestPath(3, 2)); // Output: 6
44        System.out.println(graph.shortestPath(0, 3)); // Output: -1
45        graph.addEdge(new int[]{1, 3, 4});
46        System.out.println(graph.shortestPath(0, 3)); // Output: 6
47    }
48}