11.3.1 다익스트라 알고리즘 구현

이번에는 다익스트라 알고리즘을 구현해 보아요. 그래프와 Heuristic 부분은 깊이 우선 탐색과 너비 우선 탐색에서 구현한 것과 매우 흡사합니다.

먼저 간선 클래스를 정의합시다.

두 개의 정점과 간선의 비용이 멤버로 필요하겠죠.

두 개의 정점과 간선의 비용을 입력 인자로 받게 생성자를 제공하세요.

특정 정점이 존재하는지 두 개의 정점 모두 존재하는지 판별하는 메서드를 제공하세요.

하나의 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 제공하세요.

간선 정보를 출력하는 메서드를 제공하세요.

간선의 비용을 구하는 메서드를 제공하세요.

생성자는 입력 인자로 받은 값으로 멤버 필드를 설정하게 구현하세요.

특정 정점이 존재하는지 판별하는 메서드를 구현하세요.

두 개의 정점 모두 존재하는지 판별하는 메서드를 구현하세요.

하나의 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 구현하세요.

간선의 정보를 출력하는 메서드를 구현하세요.

간선의 비용을 구하는 메서드를 구현하세요.

 

이제 그래프 클래스에 관해 정의합시다. 먼저 string 형식을 정점으로 할 거예요. 정점을 보관하는 vector를 Vertexs 이름으로 타입 재지정하세요.

Edge *를 보관하는 vector를 Edges 이름으로 타입 재지정하세요.

그래프 클래스를 정의합시다.

그래프 클래스에는 정점 집합과 간선 집합을 기억하는 멤버가 필요하겠죠.

그래프 내에서 생성한 간선들을 소멸하기 위해 소멸자를 제공하세요.

정점을 추가하는 메서드를 제공합시다.

정점이 존재하는지 판별하는 메서드를 제공합시다.

간선을 추가하는 메서드를 제공합시다.

두 개의 점점을 잇는 간선이 존재하는지 판별하는 메서드를 제공하세요.

모든 정점의 이웃 목록을 출력하는 메서드를 제공하세요.

특정 정점의 이웃 목록을 출력하는 메서드를 제공하세요.

특정 정점의 이웃 목록을 구하는 메서드를 제공하세요.

특정 정점을 끝점으로 하는 간선 집합을 구하는 메서드를 제공하세요.

소멸자에서는 간선 집합에 있는 모든 간선을 소멸하세요.

정점을 추가하는 메서드를 구현합시다.

만약 입력 인자로 받은 정점이 있으면 추가하지 않고 없을 때만 추가합니다.

정점이 존재하는지 판별하는 메서드를 구현하세요.

두 정점을 끝점으로 하는 간선을 추가하는 메서드를 구현합시다.

두 개의 정점이 모두 존재해야 합니다.

두 개의 정점을 끝점으로 하는 간선이 이미 있으면 추가하지 않습니다.

여기에서는 간선의 무게 순으로 간선 집합에 추가합시다.

처음으로 새로 추가하는 간선의 비용보다 크거나 같은 위치를 찾으세요.

위치를 찾으면 반복문을 탈출하세요.

찾은 위치에 새로운 간선을 생성하여 보관하세요.

두 개의 정점 중에 없는 정점이 있을 때는 추가하지 않았으므로 거짓을 반환하세요.

두 개의 정점을 끝점으로 하는 간선이 있는지 판별하는 메서드를 구현하세요.

모든 정점의 이웃 정점 목록을 출력하는 메서드를 구현하세요.

특정 정점의 이웃 정점 목록을 출력하는 메서드를 구현하세요.

특정 정점의 이웃 정점들을 구하는 메서드를 구현하세요.

입력 인자로 받은 정점을 포함하는 간선이 있으면 나머지 정점이 이웃입니다.

조사한 이웃 집합을 반환합니다.

특정 정점을 끝점으로 하는 간선 집합을 구하는 메서드를 제공하세요.

입력 인자로 받은 정점을 포함하는 간선이 있으면 추가하세요.

조사한 간선 집합을 반환합니다.

 

Heuristic 클래스 부분을 구현합시다. 먼저 방문한 정정 목록을 Foots로 타입 재지정하세요.

경험 정보를 보관하는 vector를 Heues로 타입 재지정할게요.

경험 정보 클래스를 구현합시다. 이 부분도 앞에서 구현한 것과 대부분 비슷합니다.

그래프와 지나온 정점 목록과 전체 비용을 멤버로 선언하세요.

그래프와 출발 정점을 입력 인자로 받습니다.

다음 경험 정보 목록을 구하는 메서드를 제공합시다.

현재까지 방문한 경로를 출력하는 메서드를 제공합시다.

현재까지 경로의 비용을 구하는 메서드를 제공하세요.

가장 마지막에 방문한 정점을 구하는 메서드를 제공하세요.

현재 경험에서 특정 정점을 추가 방문하는 생성자를 제공하세요. 이 생성자는 클래스 내부에서만 사용합니다.

생성자에서는 입력 인자로 받은 값으로 멤버를 설정하세요

전체 비용은 0으로 초기화하세요.

다음 Heuristic 목록을 조사하여 반환하는 EnumNext 메서드를 구현합시다.

현재 방문한 마지막 정점을 구합니다.

마지막 방문한 정점을 끝점으로 하는 간선 집합을 구하세요.

간선 집합을 순차적으로 순회해야죠.

반복자 위치의 간선에서 나머지 정점을 구합니다.

방문한 적이 있는지 판별하세요. 방문한 적이 없으면 나머지 정점을 방문하는 새로운 경험을 생성합니다.

새로운 경험을 비용 순으로 보관하기 위한 자리를 찾습니다.

찾은 위치에 새로운 경험을 보관하세요.

다음 경험 목록을 반환합니다.

방문한 경로를 출력하는 메서드를 구현하세요.

전체 비용과 마지막 정점을 구하는 메서드를 구현하세요.

이전 경험에서 새로운 정점을 추가 방문하는 생성자를 구현하세요.

비용은 이전 경험의 비용에 새로운 비용을 추가한 비용으로 설정하세요.

이제 다익스트라 알고리즘을 구현할 차례입니다. 우선 순위 큐에서 비교할 함수 개체를 정의하세요.

다익스트라 알고리즘은 진입점 main 함수에 작성할게요.

먼저 그래프를 생성하고 정점 및 간선을 추가하세요.weight 있는 그래프

다익스트라 알고리즘은 우선 순위 큐가 필요합니다.

그리고 각 정점으로 가는 최단 거리 후보 목록을 기억해야 합니다.

여기에서는 경험 정보를 여러 자료 구조에 보관하여 소멸의 책임을 지기 편하게 모든 경험 정보를 보관하는 별도의 자료 구조를 선언하세요.

초기 경험 정보를 생성하여 큐에 보관하세요.

큐가 빌 때까지 반복하세요.

큐에서 경험 정보를 꺼내옵니다.

꺼내온 경험 정보에서 다음 경험 목록을 조사합니다.

다음 경험 목록을 순차적으로 순회합니다.

새로운 경험 정보의 마지막 정점이 후보 테이블에 이미 있는지 확인해야 합니다.

새로운 경험 정보의 마지막 정점을 구하세요.

교체하지 않았는지 판별하는 변수를 true로 초기화하세요.

후보 테이블을 순회합니다.

반복자의 위치의 경험 정보에서 마지막 정점을 구합니다.

새로운 경험 정보의 마지막 정점과 후보 테이블의 현재 경험 정보의 마지막 정점이 같은지 확인해야죠.

만약 후보 테이블의 전체 비용이 더 크면 교체해야 하므로 check를 false로 변경하세요.

반복문을 탈출합니다.

만약 hseek가 hlast와 같다는 것은 후보 테이블에 없는 것입니다.

우선 순위 큐와 후보 테이블에 보관합니다.

후보 테이블에 있을 때는 교체해야 하는지를 확인하세요. check가 false면 교체해야 합니다.

후보 테이블에서 제거하세요.

후보 테이블에 새로운 경험으로 보관하세요.

우선 순위 큐에도 보관합니다.

후보 테이블에는 출발지에서 나머지 모든 정점으로 가는 최단 경로가 남아있습니다.

사용했던 모든 경험 정보를 소멸하세요.

▷ 실행 결과