LeetCode: Network Delay Time Bellman Ford 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.

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N]. The
3. length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Please review for performance

   [TestClass]
    public class NetworkDelayTimeTest
    {
        [TestMethod]
        public void ExampleTestBellmanFord()
        {
            int N = 4;
            int K = 2;
            int[][] times = { new[] { 2, 1, 1 }, new[] { 2, 3, 1 }, new[] { 3, 4, 1 } };
            NetworkDelayTimeBellmanFord bellmanFord = new NetworkDelayTimeBellmanFord();
            Assert.AreEqual(2, bellmanFord.NetworkDelayTime(times, N, K));
        }
    }


  public class NetworkDelayTimeBellmanFord
    {
        public int NetworkDelayTime(int[][] times, int N, int K)
        {
            var dist = Enumerable.Repeat(int.MaxValue, N + 1).ToList();
            dist[K] = 0;
            for (int i = 0; i < N; i++)
            {
                foreach (var e in times)
                {
                    int u = e[0];
                    int v = e[1];
                    int w = e[2];
                    if (dist[u] != int.MaxValue && dist[v] > dist[u] + w)
                    {
                        dist[v] = dist[u] + w;
                    }
                }
            }

            int maxWait = 0;
            for (int i = 1; i <= N; i++)
            {
                maxWait = Math.Max(maxWait, dist[i]);
            }

            if (maxWait == int.MaxValue)
            {
                return -1;
            }

            return maxWait;
        }
    }

Answer 1

You can optimize a bit by make it possible to step out of the first outer loop if the inner foreach-loop doesn't make any changes to dist in one iteration.

---

Wouldn't it be possible to test for maxWait whenever you update dist[v] in the foreach-loop:

{
    dist[v] = dist[u] + w;
    maxWait = Math.Max(maxWait, dist[v]);
}

This may og may not be an optimization - depending on the cost of comparing two integers potentially N * N times compared to the cost of an extra loop comparing them N-1 times?

---

You could make an early return in the find-max-loop:

       int maxWait = 0;
        for (int i = 1; i <= N; i++)
        {
          maxWait = Math.Max(maxWait, dist[i]);

          if (maxWait == int.MaxValue)
          {
            return -1;
          }
        }

or change it to:

int maxWait = dist.Skip(1).Max();
return maxWait < int.MaxValue ? maxWait : -1;