다익스트라 알고리즘 (Dijkstra)시작점에서 각 노드가지의 최소 비용을 계싼하는 알고리즘이다.각 노드를 탐색하며, 해당 지점까지 온 비용(g)이 가장 작은 노드부터 탐색한다.그러므로 목표까지 가까워 보이는 방향을 추정하지 않고, 그저 현재까지 누적된 비용이 가장 작은 노드만을 기준으로 탐색한다. 위 이미지는 다익스트라가 길을 찾는 방식이다.가까운 곳에 목표가 있음에도 원형으로 퍼져나가며 경로를 찾는 비효율적인 모습을 보인다. 다익스트라를 코드로 구현하면 다음과 같다. using System.Collections.Generic;using UnityEngine;class DijkstraNode{ public int Index; // ABCD, 0123 번호 public Ve..

가중치 그래프 ( Weighted Graph )그래프란 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조를 말한다.Vertex연결되어 있는 개체지하철 역, 도시, 웹페이지 등Edge정점 간의 관계두 역 사이의 이동 가능선Weight (가중치)간선에 부여된 값이동 시간, 거리, 요금 등 그래프란 정점들 간의 관계를 표현한 네트워크 구조 라고 할 수 있다.그리고 기본 그래프는 Vertex와 Edge만으로 이루어져 있기 때문에 연결의 유무만을 표현한다. 여기서 가중치를 더한 것이 가중치 그래프다.두 역 사이의 연결만을 표현하는 것이 아닌 이동 시간과 같은 가중치를 포함하는 경우를 말한다. 다익스트라 알고리즘 (Dijkstra's Algorithm)음의 가중치가 없는 그래프에서 최단 경로를 탐색하는 알..