Dijkstra's Algorithm Approach

Dijkstra's algorithm is suitable for finding the shortest paths from a single source node to all other nodes in a weighted graph with non-negative weights. For the network delay problem, we aim to determine the maximum shortest-path distance from the source node k to every other node. If any node remains unreachable, the result is -1.

The implementation below uses an adjacency matrix to represent the graph. The algorithm iteratively selects the unvisited node with the smallest known distance, marks it as visited, and relaxes the distances of its neighbors.

C++ Implementation

class Solution {
public:
    int networkDelayTime(vector& times, int n, int k) {
        const int INF = 1e9;
        vector graph(n + 1, vector<int>(n + 1, INF));
        vector<int> minDist(n + 1, INF);
        vector<bool> visited(n + 1, false);

        for (const auto& t : times) {
            graph[t[0]][t[1]] = t[2];
        }

        minDist[k] = 0;
        int maxTime = 0;

        for (int i = 1; i <= n; ++i) {
            int u = -1;
            for (int v = 1; v <= n; ++v) {
                if (!visited[v] && (u == -1 || minDist[v] < minDist[u])) {
                    u = v;
                }
            }

            if (minDist[u] == INF) return -1;

            visited[u] = true;
            maxTime = max(maxTime, minDist[u]);

            for (int v = 1; v <= n; ++v) {
                if (graph[u][v] != INF) {
                    minDist[v] = min(minDist[v], minDist[u] + graph[u][v]);
                }
            }
        }
        return maxTime;
    }
};

Python Implementation

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        INF = float('inf')
        adj = [[INF] * (n + 1) for _ in range(n + 1)]
        dist = [INF] * (n + 1)
        visited = [False] * (n + 1)

        for u, v, w in times:
            adj[u][v] = w

        dist[k] = 0
        max_delay = 0

        for _ in range(n):
            u = -1
            for v in range(1, n + 1):
                if not visited[v] and (u == -1 or dist[v] < dist[u]):
                    u = v
            
            if dist[u] == INF:
                return -1
            
            visited[u] = True
            max_delay = max(max_delay, dist[u])
            
            for v in range(1, n + 1):
                if adj[u][v] != INF:
                    dist[v] = min(dist[v], dist[u] + adj[u][v])
                    
        return max_delay

Floyd-Warshall Algorithm Approach

The Floyd-Warshall algorithm computes the shortest paths between all pairs of vertices in a weighted graph. Unlike Dijkstra, it can handle negative weight edges (though not negative cycles). It uses a dynamic programming approach where the distance between nodes i and j is updated by considering node m as an intermediate point.

For this specific problem, after computing all-pairs shortest paths, we only need to examine the row corresponding to the source node k to find the maximum delay.

C++ Implementation

class Solution {
public:
    int networkDelayTime(vector& times, int n, int k) {
        const int INF = 1e9;
        vector dist(n + 1, vector<int>(n + 1, INF));

        for (int i = 1; i <= n; ++i) dist[i][i] = 0;
        for (const auto& t : times) dist[t[0]][t[1]] = t[2];

        for (int m = 1; m <= n; ++m) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (dist[i][m] != INF && dist[m][j] != INF) {
                        dist[i][j] = min(dist[i][j], dist[i][m] + dist[m][j]);
                    }
                }
            }
        }

        int result = 0;
        for (int i = 1; i <= n; ++i) {
            if (dist[k][i] == INF) return -1;
            result = max(result, dist[k][i]);
        }
        return result;
    }
};

Python Implementation

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        INF = float('inf')
        dist = [[INF] * (n + 1) for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            dist[i][i] = 0
            
        for u, v, w in times:
            dist[u][v] = w

        for m in range(1, n + 1):
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    if dist[i][m] != INF and dist[m][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][m] + dist[m][j])

        max_time = 0
        for i in range(1, n + 1):
            if dist[k][i] == INF:
                return -1
            max_time = max(max_time, dist[k][i])
        
        return max_time