[💬] 다익스트라 알고리즘이 그렇게 어려운게 아니네

[익명(0ydc7dxcobzi)]

근데 이거 내가 잘못 이해한게 아니라면

정점 A부터 G까지 있는 맵에서

A - D 까지만의 최단거리를 계산하고 싶어도

G(모든 정점)까지 다 계산해야 답을 알 수 있는 알고리즘 같은데

맞음?

[익명(14.52)]

최소거리 그래프를 늘려가는 식이라서 별다른걸 안하면 목적지에 도달하는 순간 끝나지 않나?

[익명(0ydc7dxcobzi)]

설명을 보면 정점이 들어있는 큐가 비워져야 끝이라던데

[익명(14.52)]

내가 착각했나봄 최소 신장 트리쪽 로직이랑 헤깔렸다

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(0ydc7dxcobzi)]

설명을 보면 정점이 들어있는 큐가 비워져야 끝이라던데

[익명(dkxm99)]

그냥 bfs에 가중치만 추가된거라 생각하면되지 않을까싶은데, 일단 목적지 찾으면 바로 거기서 탐색 끝일껄

[익명(0ydc7dxcobzi)]

설명을 보면 정점이 들어있는 큐가 비워져야 끝이라던데

[익명(dkxm99)]

그 마지막 노드가 목적지면 맞겠지만 정점이 들어있는 큐라는게 목적지까지 경로를 말할껄

[익명(dkxm99)]

애초에 내가 백준에서 bfs랑 다익스트라 관련 문제들 풀어봤는데 while(!q.empty()) 안에 경로찾는 코드 넣어서 만약 목적지에 도달했다면 바로 큐가 비워지면서 탐색이 끝나버리는식으로 풀었었어

[익명(dkxm99)]

if(nx == x && ny == y) return vist[nx][ny]; 이런식으로 했던거같은데... 나도 1년전에 풀어본거라 잘 기억은 안난다. 암튼 정 궁금하면 백준가서 직접 풀어보는게 도움될듯

[익명(58.235)]

ㅇㅇ 그런 알고리즘이긴 한데 A-D 최단거리 같은 출발지 목적지 정해져 있는 최소 비용? 최단 거리? 구하고 싶으면 A* 알고리즘 쓰면 됨. 휴리스틱 써서 하는거라 속도도 빠름

[익명(58.235)]

하지만 빨랐죠?