2
\$\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.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

enter image description here

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)
                {
                    _dist.Add(i, int.MaxValue);
                }
                // 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;
            }
        }
    }
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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

  temp.Add((edge[1], edge[2]));
}

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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