3
\$\begingroup\$

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. enter image description here

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;
        }
    }
\$\endgroup\$
1
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.