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


  
  N will be in the range [1, 100].
  K will be in the range [1, N]. The
  length of times will be in the range [1, 6000].
  All edges times[i] = (u, v, w) will have 1 &lt;= u, v &lt;= N and 0 &lt;= w &lt;= 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 &lt; N; i++)
            {
                foreach (var e in times)
                {
                    int u = e[0];
                    int v = e[1];
                    int w = e[2];
                    if (dist[u] != int.MaxValue &amp;&amp; dist[v] &gt; dist[u] + w)
                    {
                        dist[v] = dist[u] + w;
                    }
                }
            }

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

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

            return maxWait;
        }
    }
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 &lt;= 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 &lt; int.MaxValue ? maxWait : -1;