rhino333   3년 전

풀이 자체가 틀린건지 예외처리가 안된건지 모르겠네요.


다익스트라 여러 번 돌려서 최단경로가 아닌 값이 나올 때 까지 반복했습니다.

코드는 종만북 다익스트라 참고했구요, 간선을 지우는 대신 최단 경로에 속한 정점들을 표시해서 

현재 정점과 다음 정점이 모두 최단경로에 속한 정점일 때 넘어가게 구현했습니다.

ntopia   3년 전

isShort[cur] == true  이고  isShort[next] == true  이지만

cur 에서 next 로 가는 간선은 최단경로에 포함되지 않을 수도 있습니다.

경우에 따라서는 이 간선을 고려해줘야할 것 같습니다.

rhino333   3년 전

두 정점 사이에 간성이 여러개인 경우를 말씀하시는 건가요??

ntopia   3년 전

아니요 그냥 간단한 경우로

0->1  가중치 2

1->2  가중치 2

2->3  가중치 2

0->3  가중치 10

이렇게 4개 점과 4개 간선이 있다고 하고, 0번에서 출발해 3번으로 간다고 해봅시다.

이런 경우에 답을 제대로 구하지 못할 것 같습니다.

rhino333   3년 전

아 이런 반례가 있네요

간선을 지우지 않고 정점으로 처리해보려고 했는데 

제 풀이는 이런 케이스를 처리 못하는군요.

간선을 지우는 풀이로 다시해봐야겠습니다.

감사합니다!

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