LeetCode: Network Delay Time Dijkstra's Algorithm C#

Question

https://leetcode.com/problems/network-delay-time/

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2 Output: 2 

Please review for performance and C# style. I already implemented this as DFS. LeetCode: Network Delay Time DFS solution C#

 namespace GraphsQuestions { /// <summary> /// https://leetcode.com/problems/network-delay-time/ /// </summary> [TestClass] public class NetworkDelayTimeTest { [TestMethod] public void ExampleTest() { int N = 4; int K = 2; int[][] times = { new[] { 2, 1, 1 }, new[] { 2, 3, 1 }, new[] { 3, 4, 1 } }; NetworkDelayTimeDijkstra dijkstra = new NetworkDelayTimeDijkstra(); Assert.AreEqual(2, dijkstra.NetworkDelayTime(times, N, K)); } } public class NetworkDelayTimeDijkstra { private Dictionary<int, int> _dist; public int NetworkDelayTime(int[][] times, int N, int K) { var graph = new Dictionary<int, List<List<int>>>(); //we build a dictionary // key = from vertex // values - destination and wight - NOT LIKE DFS foreach (var edge in times) { if (!graph.TryGetValue(edge[0], out var temp)) { temp = graph[edge[0]] = new List<List<int>>(); } temp.Add(new List<int> { edge[1], edge[2] }); } // all the edges get max value _dist = new Dictionary<int, int>(); for (int i = 1; i <= N; ++i) { _dist.Add(i, int.MaxValue); } // we set the origin _dist[K] = 0; bool[] visited = new bool[N + 1]; while (true) { int candNode = -1; int candDist = int.MaxValue; // find a vertex which is not visited // and has the lowest distance from all unvisited vertices for (int i = 1; i <= N; ++i) { if (!visited[i] && _dist[i] < candDist) { candDist = _dist[i]; candNode = i; } } // if canNode == -1 there are no more unvisited nodes if (candNode < 0) { break; } //mark the node as visited and Update the distance to all of the neighbors visited[candNode] = true; if (graph.ContainsKey(candNode)) { foreach (var info in graph[candNode]) { _dist[info[0]] = Math.Min(_dist[info[0]], _dist[candNode]+info[1]); } } } // we compute the max distance. // if one of the edges equals int.max // we can't reach it so we return -1; int ans = 0; foreach (var cand in _dist.Values) { if (cand == int.MaxValue) { return -1; } ans = Math.Max(ans, cand); } return ans; } } } 

Answer 1

Instead of the list-list value in

var graph = new Dictionary<int, List<List<int>>>();

you could use a named tuple:

var graph = new Dictionary<int, List<(int V, int W)>>(); foreach (var edge in times) { if (!graph.TryGetValue(edge[0], out var temp)) { temp = graph[edge[0]] = new List<(int V, int W)>(); } temp.Add((edge[1], edge[2])); } 

which will make it more clear what the elements in the graph represent.

---

 // find a vertex which is not visited // and has the lowest distance from all unvisited vertices for (int i = 1; i <= N; ++i) { if (!visited[i] && _dist[i] < candDist) { candDist = _dist[i]; candNode = i; } } 

I think the above will be a bottleneck for larger graphs, because you repeatedly check all distances even if the node has been visited. A priority queue would probably be a better choice.

---

This:

 int ans = 0; foreach (var cand in _dist.Values) { if (cand == int.MaxValue) { return -1; } ans = Math.Max(ans, cand); } return ans; 

can be simplified to:

 int ans = _dist.Values.Max(); return ans == int.MaxValue ? -1 : ans; 

But it may not be a performance improvement because of your early return if you find a int.MaxValue.