무방향 그래프에서 어떤 점A 에서 점 B까지의 최단거리는 최단거리들의 합이다. 는 맞는 말?
말이 이상해서 예시로 최대한 설명해봄
예시 )
점 1에서 점 5로 가는 최단거리가 존재한다. 이 때 1~3은 모두 참?
1. (1 5) 최단거리로 이동하는 도중 임의의 점 X Y 를 지나쳤다.
1-1 나는 X에서 Y로 ( 혹은 Y에서 X로 ) 최단거리로 이동했다.
1-2 나는 X에서 5로 최단거리로 이동했다.
1-3 나는 Y에서 5로 최단거리로 이동했다.
1-4 나는 1에서 X로 최단거리로 이동했다.
1-5 나는 1에서 Y로 최단거리로 이동했다.
1-6 따라서 (1 5) 최단거리 길이 = (1 X(혹은Y) ) + ( 1 Y(혹은X) ) + ( X(혹은Y) 5 ) 라고 볼 수 있다.
2. 1에서 5로 최단거리로 이동하면서 임의의 점 K를 지났다고 하자.
1 ~ 5 의 최단거리 = 1 ~ K 까지의 최단거리 + K에서 5까지의 최단거리
3. 위 내용은 방향 그래프에서는 성립하지 않는다.
뭔가 멍청한 질문하는 거 같긴한데 제가 좀 멍청함
다익스트라에 대한 완전한 이해를 못했읍니다
3아님
1, 2는 맞음
방향 그래프에서도 성립해요?
ㅇㅇ
1->2->3->4->5 로 이동하는게 1->5로 가는 최단거리(4), 각 간선의 가중치가 1입니다 , 실제 그래프는 4->2 가중치가 1인 간선이 하나 더 있는 경우 X = 2, Y = 4 라고 하면, 1-1 ( Y에서 X로 최단거리로 이동하였다 ) 는 성립안하는거 아님? 이동은 234 로 해서 가중치 2로 이동했는데 , 4에서 2로 이동하는 최단거리는 1이 되는거 아닌가해서 3번을 넣었는데 뭔가 오류가 있나요
먼저 도달한 정점에서 진행하는게 아니라 도착할 시점을 기준으로 진행해야 함
'먼저 도달한 정점에서 진행하는게 아니라 도착할 시점을 기준으로 진행해야 함' 이 100% 이해는 안되는데 먼저 도달한 정점 = 2 에서 진행 X , 도착할 시점 = 4 기준으로 진행해야 한다. 라고 이해하면 되나요 방향 그래프에서는 2->4 로 가는 최단경로와 4->2 가는 최단 경로가 다르기 때문에 ?
ㅇㅇ
감사합니다 선생님