Dijkstra

Template

It is very similar to BFS, but we use heap

Practice questions

합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413

def solution(n, s, a, b, fares):
    distance = [int(10e9) for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]
    for fare in fares:
        start,end,cost = fare
        graph[start].append((cost,end))
        graph[end].append((cost,start))
    heap = []
    heappush(heap, [0,s])
#     distance[s]=0

    while heap:
        cost, now = heappop(heap)
        if distance[now]<cost:
            continue
        for ncost, nnext in graph[now]:
            if cost+ncost < distance[nnext]:
                distance[nnext] = cost+ncost
                heappush(heap, (cost+ncost,nnext))
    print(distance[a])
    print(distance[b])

This prints out the shortest distance from starting point (s) to a and b respectively.

My initial thinking and code is this. First make a distance list via dijkstra that tells the distance of each node from each starting point. We are gonna add this distance when we dijkstra on each node.

from heapq import heappush,heappop

def solution(n, s, a, b, fares):
    distance = [int(10e9) for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]
    minA = int(10e9)
    minB = int(10e9)
    ans = int(10e9)

    for fare in fares:
        start,end,cost = fare
        graph[start].append((cost,end))
        graph[end].append((cost,start))

    alter_distance = dijkstra(graph,n,s)
    alter_distance_copy = list(alter_distance)

    for i in range(1,n+1):
        heap = []
        heappush(heap, [0,-1,i])
        heappush(heap, [0,-2,i])
        temp_distance = alter_distance_copy
        temp_distance[i]=0

        while heap:
            cur_cost, charac, curr_node = heappop(heap)
            # print(curr_node)
            if curr_node == a and charac == -1:
                minA = min(minA, cost)
                print("minA",minA)
            elif curr_node == b and charac == -2:
                minB = min(minB,cost)
                print("minB",minB)
            if temp_distance[curr_node]<cur_cost:
                continue
            for new_cost, new_end in graph[curr_node]:
                cost = cur_cost + new_cost
                if temp_distance[new_end]>cost:
                    temp_distance[new_end] = cost
                    heappush(heap, [new_cost,charac, new_end])
        ans = min(ans, alter_distance[i] +minA +minB)
    print(ans)
    return ans
#     return distance[s]+minA+minB



def dijkstra(graph,n,s):
    alter_distance = [int(10e9) for _ in range(n+1)]
    toot =[]
    heappush(toot,(0,s))
    alter_distance[s]=0
    while toot:
        curr_cost, curr_node = heappop(toot)
        if alter_distance[curr_node]<curr_cost:
            continue
        for new_cost, new_end in graph[curr_node]:
            cost = curr_cost + new_cost
            if cost<alter_distance[new_end]:
                alter_distance[new_end] = cost
                heappush(toot, (cost,new_end))
    print(alter_distance)
    return alter_distance

solution(6,	4	,6	,2,	[[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]])

but actually we can reuuse the dijkstra without remaking it again to make distance list.

like this: btw VERY CAREFUL to make fresh distance list of infinity values each time dijkstra is performed. If you just pass distance to dijkstra parameter like

dijkstra(n,s,k,graph,distance)

then the same distance list will be used on consecutively by multiple dijkstras without being freshly created.

from heapq import heappush,heappop

def solution(n, s, a, b, fares):
    distance = [int(10e9) for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]
    ans = int(10e6)
    for fare in fares:
        start,end,cost = fare
        graph[start].append((cost,end))
        graph[end].append((cost,start))
    result = []
    for k in range(1,n+1):
        if k!=s:
            dist_s_to_node = dijkstra(n,s,k,graph)
            dist_node_to_a = dijkstra(n,k,a,graph)
            dist_node_to_b = dijkstra(n,k,b,graph)
            result.append(dist_s_to_node+ dist_node_to_a+ dist_node_to_b)
        else:
            dist_s_to_a = dijkstra(n,k,a,graph)
            dist_s_to_b = dijkstra(n,k,b,graph)
            result.append(dist_s_to_a+dist_s_to_b)
    return min(result)
    
def dijkstra(n,s,end,graph):
    heap = []
    distance = [int(10e9) for _ in range(n+1)]
    heappush(heap, [0,s])
    distance[s]=0

    while heap:
        cost, now = heappop(heap)
        if distance[now]<cost:
            continue
        for ncost, nnext in graph[now]:
            if cost+ncost < distance[nnext]:
                distance[nnext] = cost+ncost
                heappush(heap, (cost+ncost,nnext))
    # print(distance[end])
    return distance[end]

You can use Floyd-Marshall:

# 플로이드-와샬
from math import inf


def solution(n, s, a, b, fares):
    # 0부터 시작하는 인덱스
    s, a, b = s - 1, a - 1, b - 1

    # inf 로 초기화된 거리행렬
    # 자기 자신으로 가는 간선 가중치는 0
    graph = [[inf] * n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0     

    # 거리행렬에 주어진 비용 넣기
    for fare in fares:
        u, v, w = fare
        graph[u - 1][v - 1] = graph[v - 1][u - 1] = w

    # 플로이드-와샬
    for k in range(n):          # 1. 모든 노드를 중간점(경로)으로 가정하면서
        for i in range(n):      # 2. 거리행렬을 순회
            for j in range(n):  # 3. 현재 거리행렬에 저장된 거리가 k를 거쳐가는 거리보다 멀면 갱신
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                # graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) 시간 거의 두 배 걸림..

    # 출발점을 기준으로 어떤 지점 k를 거쳐 각각 a와 b로 가는 최소 비용을 탐색
    ans = inf
    for k in range(n):
        ans = min(ans, graph[s][k] + graph[k][a] + graph[k][b])

    return ans