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.