# LeetCode: Network Delay Time Dijkstra's Algorithm 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.

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)
{
}
// 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;
}
}
}


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

}


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.