[자료구조] 다익스트라 알고리즘

소개글

프로그램은 C언어로 작성되어있습니다.

목차

Dijkstra algorithm을 이용한 routing table 출력하기
1.입력값
2.프로그램
* 다익스트라 알고리즘
3.출력결과

본문내용

다익스트라에서는 출발노드에서 가장 가까운 중간노드를 하나씩 포함하면서 그 노드들로 부터 최단거리를 따져간다. touch배열은 중간노드로 포함 여부를 나타낼 변수이고 vnear는 목적지 노드까지 가는 경로에서 목적지 노드 바로 직전에 거쳐오는 노드의 인덱스를 말한다.
초기 라우팅 테이블을 초기화하기 위해 모든 경로를 따져본다. 출발노드는 자신이 목적지가 될 수 없고 이미 중간노드로 포함된 것이다. 중간노드로 포함이 된 상태를 0으로 두고 노드로 포함되지 않는 것을 1로 둔다. 첫 최단거리는 무한대로 초기화하고 모든 노드를 따져 중간노드로 포함할 최단거리(length)를 찾아 그 값과 인덱스(vnear)를 저장한다. 이렇게 해서 중간노드가 정해지면 이 중간노드를 거쳐서 목적지로 가는 기존의 경로길이를 비교해야한다. 중간노드로 포함이 안되고 중간노드를 경유하는 것이 짧다면 그 노드의 최단거리를 지난 거리로 갱신하고 그 노드로 가지 직전에 경유한 노드는 vnear라는 인덱스 노드가 갱신된다. 그런 후, 중간노드로 선택된 노드를 touch를 이용해서 포함되었음을 표시해둔다.

참고 자료

없음