Design Graph With Shortest Path Calculator

1using System;
2using System.Collections.Generic;
3
4public class Graph {
5    private int n;
6    private List<List<(int, int)>> adj;
7
8    public Graph(int n, int[][] edges) {
9        this.n = n;
10        this.adj = new List<List<(int, int)>>();
11        for (int i = 0; i < n; i++) {
12            adj.Add(new List<(int, int)>());
13        }
14        foreach (var edge in edges) {
15            adj[edge[0]].Add((edge[1], edge[2]));
16        }
17    }
18
19    public void AddEdge(int[] edge) {
20        adj[edge[0]].Add((edge[1], edge[2]));
21    }
22
23    public int ShortestPath(int node1, int node2) {
24        int[] dist = new int[n];
25        Array.Fill(dist, int.MaxValue);
26        dist[node1] = 0;
27
28        var pq = new SortedSet<(int Distance, int Vertex)>(Comparer<(int, int)>.Create((x, y) => {
29            int result = x.Distance.CompareTo(y.Distance);
30            return result == 0 ? x.Vertex.CompareTo(y.Vertex) : result;
31        }));
32        pq.Add((0, node1));
33
34        while (pq.Count > 0) {
35            var current = pq.Min;
36            pq.Remove(current);
37            int u = current.Vertex;
38            int curDist = current.Distance;
39
40            if (u == node2) return curDist;
41            if (curDist > dist[u]) continue;
42
43            foreach (var (v, cost) in adj[u]) {
44                if (dist[u] + cost < dist[v]) {
45                    dist[v] = dist[u] + cost;
46                    pq.Add((dist[v], v));
47                }
48            }
49        }
50        return -1;
51    }
52
53    public static void Main() {
54        int[][] edges = new int[][] { new int[] { 0, 2, 5 }, new int[] { 0, 1, 2 }, new int[] { 1, 2, 1 }, new int[] { 3, 0, 3 } };
55        Graph g = new Graph(4, edges);
56        Console.WriteLine(g.ShortestPath(3, 2)); // Output: 6
57        Console.WriteLine(g.ShortestPath(0, 3)); // Output: -1
58        g.AddEdge(new int[] { 1, 3, 4 });
59        Console.WriteLine(g.ShortestPath(0, 3)); // Output: 6
60    }
61}

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}