# 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:

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;
}
}


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;