[일반] 가중치 다른 bfs문제

[익명(14.36)]

가중치가 예를 들어 1, 2, 3 이렇게 세 개면  queue 세 개 만들어서 푸나요?

[익명(skuld88)]

다익스트라

[익명(106.101)]

다익스트라 - dc App

[익명(skuld88)]

출발지와 도착지가 하나밖에 없으면 다익스트라 말고 좀더 빠른 비슷한 알고리즘으로 가능함

[익명(123.143)]

0-1 BFS라고 찾아보세요

[익명(112.186)]

근데 그건 말 그대로 0, 1만 가능함

[익명(119.202)]

보는 level의 수가 작은 상수개라는 사실을 이용하면 유사하게 선형에 해결 가능할 것 같긴 함 (아니면 간선을 1짜리 1,2,3개로 분할해도 되고)

[익명(58.142)]

0, 1 아니어도 이 아이디어를 응용하면 가지수가 적은 가중치에 적용할 수 있습니다 근데 구현이 복잡해서 걍 일반적인 다익스트라 돌리는게 편함

[oseri(amoserimus)]

정점분할하는 것도 방법일듯?

[blobfacepalm(tlsdydaud1)]

그걸 Dial's algorithm이라고 함

[익명(180.70)]

다익이 제일 무난한 방법일듯