What is the best way to solve Dijkstra?

The optimized O(1) approach using Graphs patterns is generally preferred.

DSA 섹션쉬움

데이크스트라

'Dijkstra' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

가중치 그래프의 시작 노드 start에서 다른 모든 노드까지의 최단 경로를 계산하는 함수 dijkstra(graph, start)을 작성하세요. 그래프는 사전의 인접 목록으로 표시됩니다. 여기서 graph[u][v]는 u에서 v까지의 방향 간선의 가중치입니다. 최단 거리의 사전을 반환합니다.

제약

•1 <= V <= 1000
•0 <= E <= 5000
•Weights are non-negative integers.

예

Example 1

Input

graph = {0: {1: 4, 2: 1}, 1: {3: 1}, 2: {1: 2, 3: 5}, 3: {}}, start = 0

Output

{0: 0, 1: 3, 2: 1, 3: 4}

Explanation

Shortest distance from 0 to 1 is 3 (via 0->2->1).

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

import heapq
def dijkstra_opt(graph, start):
    return dijkstra_brute(graph, start)

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

import heapq
def dijkstra_brute(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        curr_dist, curr_node = heapq.heappop(pq)
        if curr_dist > distances[curr_node]: continue
        for neighbor, weight in graph[curr_node].items():
            dist = curr_dist + weight
            if dist < distances[neighbor]:
                distances[neighbor] = dist
                heapq.heappush(pq, (dist, neighbor))
    return distances