글 읽기 - 다익스트라 알고리즘 BFS를 통해선 구현 불가능인가요? (파이썬)

jmj0714 3년 전 0

다익스트라 알고리즘을 힙구조가 아닌 BFS를 통해 구현해보려 시도중입니다.

예제도 정상 작동하고 질문 글에 있던 반례들도 작동하는데

런타임에러가 꾸준히 생기네요...

혼자 힘으론 힘에 붙여 도움을 구해봅니다.

#### 다익스트라 최소 정렬

def djikstra(queue):
  if queue:
    current = queue[0] #current는 현재의 위치
    visited[current] = True
    for i,j in graph[current]: #i는 방문 할 노드 j는 해당 노드까지의 가중치
      if distance[current] + j < distance[i]:
        distance[i] = distance[current] + j
      if(i not in queue and visited[i] == False):
        queue.append(i)
    queue = sort_queue(queue[1:]) #맨 앞에 요소 = 최단거리를 가진 노드           
    djikstra(queue)
   
   
    
def sort_queue(queue): #큐에 있는 요소들을 가중치를 기준으로 정렬
   dist = {}
   for i in queue:
    dist[i] = distance[i]
   dist = sorted(dist.items(), key = lambda item: item[1]) 
   order = []
   for i,j in dist:
        order.append(i)
   return order

if __name__ == '__main__':
  INF = float('inf')
  n,m = map(int,input().split(' '))
  start = int(input()) - 1
  graph = [[] for i in range(n)]
  for j in range(m):
    u,v,w = map(int,input().split())
    graph[u - 1].append((v-1, w))             
  visited = [False for i in range(n)]
  distance = [INF] * n
  for i,j in graph[start]:
    distance[i] = j   #거리에 시작점 기준의 거리 입력
  distance[start] = 0  
  djikstra([start])
  for k in (distance):
    if k == INF: k = 'INF'
    print(k)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다익스트라 알고리즘 BFS를 통해선 구현 불가능인가요? (파이썬)

jmj0714 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말