Weighted Graphs

The type of edges of a Graph allows us to defined either Directed or Undirected graphs. However, the edges could also have weights, which represent the cost of moving between the vertices connected by these edges.

Shortest Path

We cannot use the standard BFS traversal to calculate the shortest path between two vertices. In fact, this implementation simply assumes the same cost for each edge, which is not true for weighted ones.

To overcome this problem, we could use some well-known algorithms.

For all of them, we are using the Network Delay Time problem to apply such algorithms.

Bellman–Ford algorithm

The Bellman–Ford algorithm can be applied to Graphs that have both positive and negative edges. However, it is slower compared to other ones. In fact, the algorithms runs in $O(|V||E|)$ time.

from collections import deque
from typing import Dict, List, Tuple


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = self.get_adjacency_list(times, n)

        return self.bfs(graph, k)

    def bfs(self, graph: Dict[int, List[Tuple[int, int]]], root: int) -> int:
        queue = deque([root])
        # the first node is `1`, not `0`
        # hence, for simplicity, we create a list of `n + 1` values
        distances = [float("inf")] * (len(graph) + 1)
        distances[root] = 0
        # we have to exclude it once we calculate the maximum below
        distances[0] = float("-inf")

        while queue:
            node = queue.popleft()
            for neighbor, weight in graph[node]:
                new_distance = distances[node] + weight
                if distances[neighbor] <= new_distance:
                    continue

                queue.append(neighbor)
                distances[neighbor] = new_distance

        ans = max(distances)
        return -1 if ans == float("inf") else ans

    def get_adjacency_list(
        self, times: List[List[int]], n: int
    ) -> Dict[int, List[Tuple[int, int]]]:
        graph: Dict[int, List[Tuple[int, int]]] = {i: [] for i in range(1, n + 1)}

        for a, b, weight in times:
            graph[a].append((b, weight))

        return graph

Dijkstra's algorithm

The Dijkstra's algorithm can be applied to Graphs that have only positive edges. However, it is faster compared to the Bellman–Ford algorithm. In fact, the algorithms runs in $O((|V|+|E|)log(|V|))$ time.

import heapq
from typing import Dict, List, Tuple


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = self.get_adjacency_list(times, n)

        return self.bfs(graph, k)

    def bfs(self, graph: Dict[int, List[Tuple[int, int]]], root: int) -> int:
        queue = [(0, root)]
        # the first node is `1`, not `0`
        # hence, for simplicity, we create a list of `n + 1` values
        distances = [float("inf")] * (len(graph) + 1)
        distances[root] = 0
        # we have to exclude it once we calculate the maximum below
        distances[0] = float("-inf")

        while queue:
            _, node = heapq.heappop(queue)
            for neighbor, weight in graph[node]:
                new_distance = distances[node] + weight
                if distances[neighbor] <= new_distance:
                    continue

                heapq.heappush(queue, (new_distance, neighbor))
                distances[neighbor] = new_distance

        ans = max(distances)
        return -1 if ans == float("inf") else ans

    def get_adjacency_list(
        self, times: List[List[int]], n: int
    ) -> Dict[int, List[Tuple[int, int]]]:
        graph: Dict[int, List[Tuple[int, int]]] = {i: [] for i in range(1, n + 1)}

        for a, b, weight in times:
            graph[a].append((b, weight))

        return graph