g-h를 걸치는 경로와 g-h를 걸치지 않는 경로가 있을 때 둘의 가중치가 같다면 문제가 생길 수도 있습니다.

다익스트라가 찾아주는 경로가 반드시 전자라는 보장이 있나요?

몇번 곱씹어 생각하니 그러네요 좋은 조언 감사합니다!!

가중치가 같을 때에 지금까지 g-h 지남 여부에 대해 or 연산을 하면 해결 됩니다. 이게 더 빠름.

 다익스트라가 찾아주는 경로가 g-h를 거치게끔 보장할 수 있습니다.

priority queue를 maxheap으로 설정하고 경로업데이트를 할때마다 업데이트된 거리가 기존거리와 같은 것까지 포함하여 <-업데이트된 거리, 노드번호, g-h 지남여부> 튜플을 push 합니다. 

거리, 노드번호가 같을 때 g-h 지남여부가 true인것부터 pq 에서 pop되게 하면 항상 g-h를 거치는 최단거리를 선택하게 됩니다.

g-h 거치지 않는 최단거리선택후 g-h 거치는 가중치 같은 최단거리가 이후 pq에 추가될 수 있지 않냐 라고 의문을 가질수 있는데 간선의 길이가 0보다 클경우 다익스트라에서 불가능하다는 것을 알 수 있습니다. 

즉 다익스트라 한번으로 문제 풀이가능합니다.