인터넷에서이 질문에 대한 어떤 표시도 찾을 수 없습니다. 시험에 응시 할 때 시간이 부족합니다. 질문은 매우 간단하며 모든 설명은 환영 할만한 답변입니다. 또는 아니오).최단 경로 및 Dijkstra 알고리즘
Dijkstra 알고리즘의 경우 그래프를 강하게 연결해야합니까? 모든 vertice는 다른 vertice에서 도달 할 수 있습니까? 아니면 도달 할 수없는 꼭짓점을 가질 수 있습니까? 따라서 알고리즘을 사용하여 다른 노드에서 시작해야합니까?
이 질문에 추가하려면 : Dijkstra의 알고리즘은 무향 그래프에만 적용됩니까? 내 교과서의 모든 예는 방향이 지정되지 않은 가장자리와 관련이 있습니다.
기본적으로 방향이 지정되지 않은 그래프는 방향 그래프이지만 양방향 연결입니다. 따라서 Dijkstra의 은도 방향 그래프에 적용 할 수 있습니다.
약 연결된 그래프의 경우에는 다릅니다.
그래프 섹션 A와 그래프 섹션 B가 있다고 가정 해보십시오. A에서 B로 이동할 수는 있지만 B에서 A로 이동할 수는 없다고 가정 해보십시오. A에서 시작하여 B 로의 최단 경로를 찾으려면 Dijkstra가 작동합니다. 그러나 자연스럽게 B에서 시작하여 노드에서 경로를 찾을 수 없습니다.
감사합니다. 알고리즘이 강력한 연결 및 양방향 그래프에서만 작동한다고 가정하고 싶지 않았습니다. – JmanxC
@JmanxC 미래에는 이런 것들에 대해 혼란 스러울 때마다 그래프를 작성하고 알고리즘이 어떻게 작동 하는지를 확인하는 것이 좋습니다. 약간의 정신적 노력이 필요하지만 일반적으로 특정 그래프의 경우 온라인으로 검색하는 것보다 빠르게 결과를 산출합니다. – technokrat
"나는 시간이 없어 시험에 들었어"... 그게 속임수 아닌가? –
@RobMurray 그가 실제 시험이 아닌 시험 주간을 의미 할 수도 있습니다. – technokrat
Dijkstra 's algorithmc은 DIRECTED 그래프에 적용됩니다 –