🟡 Graph Algorithms: Network Latency Optimization

AIVIA Project Engine Coding Challenges
1

Graph Algorithms: Network Latency Optimization

Difficulty: Medium

Problem Statement

You are tasked with optimizing a content delivery network (CDN). The network is represented as a weighted directed graph, where:

  • Nodes represent servers, identified by unique non-negative integer IDs (not necessarily consecutive).
  • Edges represent direct connections between servers.
  • Weights represent latency (in milliseconds) between servers.

Your goal is to find the path with the minimum total latency from a given source server to a target server. If there is no path between the source and target servers, report that no such path exists.

Implementation Details

Implement the following function:

from typing import List, Tuple

def find_fastest_route(servers: List[List[int]], source: int, target: int) -> Tuple[int, List[int]]:
    """
    Find the path with minimum total latency between source and target servers.

    Args:
        servers (List[List[int]]): A list of edges, where each edge is represented as [from_server, to_server, latency].
        source (int): The ID of the starting server.
        target (int): The ID of the target server.

    Returns:
        Tuple[int, List[int]]: A tuple (total_latency, path), where:
            - total_latency is the sum of latencies along the fastest path.
            - path is a list of server IDs representing the path from source to target.
        If no path exists, return (float('inf'), []).
    """
    pass  # Your implementation here

Constraints

  • Number of Servers (Nodes): (1 \leq N \leq 10^4)
  • Latency Values (Edge Weights): (0 \leq \text{latency} \leq 1000)
  • Server IDs: Non-negative integers (not necessarily consecutive)
  • Graph: Directed and may not be fully connected
  • No Negative Latencies

Example Usage

network = [
    [0, 1, 5],  # Server 0 to Server 1 with 5ms latency
    [0, 2, 2],  # Server 0 to Server 2 with 2ms latency
    [1, 3, 4],  # Server 1 to Server 3 with 4ms latency
    [2, 1, 1],  # Server 2 to Server 1 with 1ms latency
    [2, 3, 6],  # Server 2 to Server 3 with 6ms latency
]

latency, path = find_fastest_route(network, 0, 3)
print(f"Minimum latency: {latency}ms")  # Expected Output: Minimum latency: 7ms
print(f"Path taken: {path}")             # Expected Output: Path taken: [0, 2, 1, 3]

Test Cases

def test_find_fastest_route():
    # Test Case 1: Direct path is not the fastest
    network1 = [
        [0, 3, 10],  # Direct but slower
        [0, 1, 2],
        [1, 2, 2],
        [2, 3, 2],
    ]
    assert find_fastest_route(network1, 0, 3) == (6, [0, 1, 2, 3])

    # Test Case 2: Disconnected servers
    network2 = [
        [0, 1, 5],
        [2, 3, 4],
    ]
    assert find_fastest_route(network2, 0, 3) == (float('inf'), [])

    # Test Case 3: Circular path should not affect result
    network3 = [
        [0, 1, 2],
        [1, 2, 2],
        [2, 1, 1],  # Creates a cycle
        [1, 3, 3],
    ]
    assert find_fastest_route(network3, 0, 3) == (5, [0, 1, 3])

    # Test Case 4: Source and target are the same
    network4 = [
        [0, 1, 2],
        [1, 2, 2],
    ]
    assert find_fastest_route(network4, 0, 0) == (0, [0])

    # Test Case 5: Multiple paths with same total latency
    network5 = [
        [0, 1, 2],
        [0, 2, 2],
        [1, 3, 2],
        [2, 3, 2],
    ]
    latency, path = find_fastest_route(network5, 0, 3)
    assert latency == 4
    assert path in ([0, 1, 3], [0, 2, 3])  # Either path is acceptable

    print("All test cases pass!")

Expected Solution Approach

To efficiently solve this problem, implement Dijkstra’s Algorithm, which is suitable for graphs with non-negative edge weights.

Algorithm Steps

  1. Graph Construction:

    • Build an adjacency list (dictionary) from the servers input for quick access to neighboring nodes.
    • Since the graph is directed, add edges accordingly.

  2. Initialization:

    • Use a priority queue (min-heap) to store nodes based on their current total latency from the source.
    • Initialize the heap with the source node and a total latency of zero.
    • Maintain a distances dictionary to keep track of the shortest known latency to each node.

  3. Processing Nodes:

    • While the priority queue is not empty:
      • Pop the node with the smallest total latency.
      • If the current node is the target, return the total latency and path.
      • Skip the node if a better (shorter) path to it has already been found.
      • For each neighbor, calculate the new total latency.
      • If the new latency is less than the known latency, update it and push the neighbor onto the heap with the updated path.

  4. Path Reconstruction:

    • Maintain the path taken to reach each node.
    • When the target is reached, return the accumulated latency and the path.

  5. No Path Scenario:

    • If the target cannot be reached after processing all nodes, return (float('inf'), []).

Time Complexity

  • Time Complexity: (O(E \log V)), where (E) is the number of edges and (V) is the number of vertices.
  • Space Complexity: (O(V + E)) for storing the graph and the distances.

Implementation Hint

You can use the heapq module in Python for the priority queue implementation. Here’s a skeleton to help you start:

from collections import defaultdict
import heapq
from typing import List, Tuple

def find_fastest_route(servers: List[List[int]], source: int, target: int) -> Tuple[int, List[int]]:
    # Build the graph
    graph = defaultdict(list)
    for u, v, w in servers:
        graph[u].append((v, w))

    # Initialize the priority queue and distances
    heap = [(0, source, [source])]  # (total_latency, current_node, path)
    distances = {source: 0}

    while heap:
        total_latency, current_node, path = heapq.heappop(heap)

        # If target is reached, return the result
        if current_node == target:
            return (total_latency, path)

        # Skip if a better path to current_node is already found
        if total_latency > distances.get(current_node, float('inf')):
            continue

        for neighbor, weight in graph.get(current_node, []):
            distance = total_latency + weight
            if distance < distances.get(neighbor, float('inf')):
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor, path + [neighbor]))

    # If target was not reached
    return (float('inf'), [])

Learning Objectives

  1. Understand Graph Representation:

    • Model networks using directed graphs and adjacency lists.
    • Differentiate between directed and undirected graphs.

  2. Implement Efficient Path-Finding Algorithms:

    • Apply Dijkstra’s Algorithm to find the shortest path.
    • Utilize priority queues (heaps) for efficient node selection.

  3. Handle Edge Cases in Network Routing:

    • Manage scenarios with disconnected nodes.
    • Handle cycles and ensure they don’t cause incorrect shortest paths.

  4. Analyze Time and Space Complexity:

    • Evaluate algorithm efficiency using Big O notation.
    • Understand the trade-offs between different data structures.

Real-World Applications

  • Content Delivery Networks (CDNs): Optimize data routing to reduce latency and enhance user experience.
  • Network Routing Protocols: Determine efficient paths in telecommunications and internet networks.
  • Traffic Optimization: Minimize travel time in transportation and logistics networks.
  • Distributed Systems Communication: Improve efficiency in message passing and data synchronization.