C언어 다익스트라 질문드립니다.

최단경로. 최단거리. 계산. 탐색 알고리즘.

//실제로 사용되는 사례는

인터넷 라우팅에서 사용되는 OSPF(Open Shortest Path First) 방식의 프로토콜과 지하철노선 탐색 어플이나 버스 환승 탐색 정보에 유용하게 쓰인다. [출처] 다익스트라 알고리즘(Dijstra)|작성자 찐호오빠

다익스트라 최단경로알고리즘

다익스트라(Dijkstra) 알고리즘의 재발견 - 진화하자 - 어디에도 소속되지 않기

뭐냐하면. (위 주소에 글을 읽고 정리해보면.)

- 고무줄 놀이처럼. 양쪽 끝 항목을 잡고. 늘려서 일자로 나오면. 그게 최단거리

- 트리로 구현할경우. 주변 항목을 깊이값 마다 붙여보고. 길이가 짧은것만 남기고. 더 길면 자르고. 같은 항목이 나오면 자르기 (미용실 머리카락 자르기 처럼...)

//이 점들을. 어떻게 트리로 만들 수 있을까?

하지만. 이런 경우에도 적용할 수 있을까... 일정한 조건에서 가능한건 아닐까... ㅡ_ㅡ;;

각 노드마다. 다 더해보면. 결과값이 나오기야 하겠지만...

- 끝점을 경유하는 항목만 남기기

- 남은 항목과 중복되면 지우기

- 항목의 끝점에서 부터. 진행되는 순서에 따라서. 트리의 깊이값으로 맞추기

마치. 종이로 된 샹드리에의 한점을 잡고. 끌어올리는 느낌이 든다.

이와 같은 예제를 DirectX 의 Cloth 와 Qt SDK 로봇에서 본것 같다.

다익스트라 알고리즘 [Dijkstra’s algorithm] 에서의 최단 경로를 구하기 위해서는

데이터 항목의 위치를 트리로 구현해야 하는데. 그 방법은 수건 집어 올리기'로 생각된다. (통발. 모기장. 잠자리채. 삿갓...)

이 방식이. 맞는지는 모르겠다. ㅡ_ㅡ;; 윗글의 블로그에 물어보니. 맞다고 알려주셨다. 뭔가 많이 얻어먹은 기분이 든다. ㅡ_ㅡ;;

블로그

지식백과

다익스트라의 은행원 알고리즘 [Dijkstra’s banker algorithm]
컴퓨터인터넷IT용어대사전 용어해설 > 컴퓨터/통신
다익스트라가 제안한 알고리즘으로, 병렬 수행 프로세스 간의 교착 상태를 방지하기 위해 프로세스가 요구한 자원의 수가 현재 사용 가능한 자원의 수보다 작을 때 프로세스가 요구한 수만큼 더 자원을... 더보기
다익스트라의 알고리즘 [Dijkstra’s algorithm]
컴퓨터인터넷IT용어대사전 용어해설 > 컴퓨터/통신
통신의 최단 경로를 결정하기 위해 경로 길이를 계산하는 알고리즘.
최단 경로 알고리즘
네이버캐스트 컴퓨터/통신 > 소프트웨어
플로이드 알고리즘은 모든 정점간의 최단 경로를 구할 수 있고, 벨만 포드 알고리즘은 가중치가 음수이더라도 최단 경로를 구할 수 있다는 장점이 있지만, 둘 다 다익스트라... 더보기
글 안성진 부제 빠른길 어떻게 찾는 것일까?