June 2024 – My Programming Notes

Monthly Archives: June 2024

C# || How To Design Graph With Shortest Path Calculator Using C#

June 01, 2024 admin No comments

The following is a module with functions which demonstrates how to design graph with shortest path calculator using C#.

1. Graph – Problem Statement

There is a directed weighted graph that consists of n nodes numbered from 0 to n – 1. The edges of the graph are initially represented by the given array edges where edges[i] = [from_i, to_i, edgeCost_i] meaning that there is an edge from from_i to to_i with the cost edgeCost_i.

Implement the Graph class:

Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

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.

2. Graph – Solution

The following is a solution which demonstrates how to design graph with shortest path calculator.





		
		
			2. Graph - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design graph shortest path calculator
// ============================================================================
/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.AddEdge(edge);
 * int param_2 = obj.ShortestPath(node1,node2);
 */
public class Graph {
    List<List<KeyValuePair<int, int>>> adjList;

    public Graph(int n, int[][] edges) {
        adjList = new List<List<KeyValuePair<int, int>>>();
        for (int i = 0; i < n; i++) {
            adjList.Add(new List<KeyValuePair<int, int>>());
        }
        foreach (int[] e in edges) {
            AddEdge(e);
        }
    }

    public void AddEdge(int[] edge) {
        adjList[edge[0]].Add(new KeyValuePair<int, int>(edge[1], edge[2]));
    }

    public int ShortestPath(int node1, int node2) {
        int n = adjList.Count;
        var pq = new PriorityQueue<List<int>, List<int>>(
            Comparer<List<int>>.Create((a, b) => a[0].CompareTo(b[0]))
        );

        int[] costForNode = new int[n];
        Array.Fill(costForNode, int.MaxValue);
        costForNode[node1] = 0;

        var root = new List<int>() { 0, node1 };
        pq.Enqueue(root, root);

        while (pq.Count > 0) {
            var curr = pq.Dequeue();
            int currCost = curr[0];
            int currNode = curr[1];

            if (currCost > costForNode[currNode]) {
                continue;
            }
            if (currNode == node2) {
                return currCost;
            }
            foreach (var neighbor in adjList[currNode]) {
                int neighborNode = neighbor.Key;
                int cost = neighbor.Value;
                int newCost = currCost + cost;

                if (newCost < costForNode[neighborNode]) {
                    costForNode[neighborNode] = newCost;
                    var newPath = new List<int>() { newCost, neighborNode };
                    pq.Enqueue(newPath, newPath);
                }
            }
        }

        return -1;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design graph shortest path calculator
// ============================================================================
/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.AddEdge(edge);
 * int param_2 = obj.ShortestPath(node1,node2);
 */
public class Graph {
    List<List<KeyValuePair<int, int>>> adjList;
 
    public Graph(int n, int[][] edges) {
        adjList = new List<List<KeyValuePair<int, int>>>();
        for (int i = 0; i < n; i++) {
            adjList.Add(new List<KeyValuePair<int, int>>());
        }
        foreach (int[] e in edges) {
            AddEdge(e);
        }
    }
 
    public void AddEdge(int[] edge) {
        adjList[edge[0]].Add(new KeyValuePair<int, int>(edge[1], edge[2]));
    }
 
    public int ShortestPath(int node1, int node2) {
        int n = adjList.Count;
        var pq = new PriorityQueue<List<int>, List<int>>(
            Comparer<List<int>>.Create((a, b) => a[0].CompareTo(b[0]))
        );
 
        int[] costForNode = new int[n];
        Array.Fill(costForNode, int.MaxValue);
        costForNode[node1] = 0;
 
        var root = new List<int>() { 0, node1 };
        pq.Enqueue(root, root);
 
        while (pq.Count > 0) {
            var curr = pq.Dequeue();
            int currCost = curr[0];
            int currNode = curr[1];
 
            if (currCost > costForNode[currNode]) {
                continue;
            }
            if (currNode == node2) {
                return currCost;
            }
            foreach (var neighbor in adjList[currNode]) {
                int neighborNode = neighbor.Key;
                int cost = neighbor.Value;
                int newCost = currCost + cost;
 
                if (newCost < costForNode[neighborNode]) {
                    costForNode[neighborNode] = newCost;
                    var newPath = new List<int>() { newCost, neighborNode };
                    pq.Enqueue(newPath, newPath);
                }
            }
        }
 
        return -1;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

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

Monthly Archives: June 2024

C# || How To Design Graph With Shortest Path Calculator Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories