เวลาหน่วงของเครือข่ายและการสร้างเส้นทางกลับคืน

ปัญหาเวลาหน่วงของเครือข่าย

วิธีแก้ปัญหา: ไดก์สตรา + ค่าสูงสุดของระยะทาง

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

การสร้างเส้นทางกลับคืนด้วยอาร์เรย์ prev

import heapq
from collections import defaultdict

def shortest_path_with_reconstruction(times, n, src, dst):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    prev = {i: None for i in range(1, n+1)}
    dist[src] = 0
    heap = [(0, src)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    
    # Reconstruct path from src to dst
    path, node = [], dst
    while node is not None:
        path.append(node)
        node = prev[node]
    return dist[dst], path[::-1]

BFS สองทิศทางสำหรับกราฟไม่มีน้ำหนักขนาดใหญ่

from collections import deque

def bidir_bfs(graph, src, dst):
    if src == dst: return 0
    
    front_q = deque([src]); front_visited = {src: 0}
    back_q = deque([dst]);  back_visited = {dst: 0}
    
    def expand(queue, visited, other_visited):
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in visited:
                visited[nxt] = visited[node] + 1
                queue.append(nxt)
                if nxt in other_visited:
                    return visited[nxt] + other_visited[nxt]
        return -1
    
    while front_q or back_q:
        res = expand(front_q, front_visited, back_visited)
        if res != -1: return res
        res = expand(back_q, back_visited, front_visited)
        if res != -1: return res
    return -1

ควรเลือกใช้อัลกอริทึมใด

หาเมืองที่มีเพื่อนบ้านซึ่งไปถึงได้น้อยที่สุด (LeetCode 1334)

def findTheCity(n, edges, distanceThreshold):
    INF = float('inf')
    dist = [[INF]*n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = dist[v][u] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    
    best_city, best_count = -1, n
    for city in range(n):
        count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
        if count <= best_count:
            best_count = count
            best_city = city
    return best_city

print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4))  # 3

เส้นทางใน DAG ที่มีน้ำหนัก

from collections import deque

def dag_shortest_path(V, edges, source):
    graph = [[] for _ in range(V)]
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    # Topological sort (Kahn's)
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    topo = []
    while queue:
        node = queue.popleft(); topo.append(node)
        for nxt, _ in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    # Relax in topological order
    dist = [float('inf')] * V
    dist[source] = 0
    for u in topo:
        if dist[u] != float('inf'):
            for v, w in graph[u]:
                dist[v] = min(dist[v], dist[u] + w)
    return dist

เส้นทางสั้นที่สุดในเมทริกซ์ที่มีสิ่งกีดขวาง

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    while queue:
        r, c, d = queue.popleft()
        if r == n-1 and c == n-1:
            return d
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
                visited.add((nr,nc))
                queue.append((nr, nc, d+1))
    return -1

print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]]))  # 4

BFS จากหลายแหล่ง

ทบทวนการเลือกอัลกอริทึม

การค้นหาเส้นทางในคำถามสัมภาษณ์งาน

ตรวจสอบความเข้าใจ

ทบทวนบทเรียน