언제나 휴일

11.3.2 다익스트라 알고리즘 코드 다음은 앞에서 구현한 다익스트라 알고리즘 코드입니다. //Edge.h#pragma once#include using namespace std;class Edge{ string vt1; string vt2; int weight;public: Edge(string vt1,string vt2,int height); bool Exist(string vt)const; bool Exist(string vt1, string vt2)const; string Other(string vt)const; void View()const; int GetWeight()const;}; //Edge.cpp#include "Edge.h"#include using namespace std; Edge:..

11.3.1 다익스트라 알고리즘 구현 이번에는 다익스트라 알고리즘을 구현해 보아요. 그래프와 Heuristic 부분은 깊이 우선 탐색과 너비 우선 탐색에서 구현한 것과 매우 흡사합니다. 먼저 간선 클래스를 정의합시다.class Edge{두 개의 정점과 간선의 비용이 멤버로 필요하겠죠. string vt1; string vt2; int weight;public:두 개의 정점과 간선의 비용을 입력 인자로 받게 생성자를 제공하세요. Edge(string vt1,string vt2,int height);특정 정점이 존재하는지 두 개의 정점 모두 존재하는지 판별하는 메서드를 제공하세요. bool Exist(string vt)const; bool Exist(string vt1, string vt2)const;하나의..

11.3 다익스트라 알고리즘 이번에는 간선의 비용이 있는 그래프에서 최단 거리를 찾는 알고리즘 중에 하나인 다익스트라 알고리즘을 살펴 보아요. 다익스트라 알고리즘은 출발 정점에서 가까운 경로 순으로 보관하는 우선 순위 큐와 출발 정점에서 특정 정점까지 최단 경로 후보들을 보관하는 후보 테이블을 이용하는 알고리즘입니다. 참고로 벨만 포드 알고리즘은 간선의 비용이 음수일 때도 적용할 수 있는 알고리즘이며 나머지는 다익스트라와 같습니다. 제일 먼저 출발 정점에서 인점한 정점을 방문하는 다음 경험 목록을 구합니다. 그리고 마지막 정점까지 가는 경로가 후보 테이블에 있는지 확인합니다. 만약 후보 테이블에 있는 경로가 새로운 경로보다 비용이 많으면 새로운 경로로 교체합니다. 처음 마지막 정점이 방문하였을 때는 후보..