- Graph 내 최단경로 문제 정의와 활용분야 및 다익스트라 알고리즘의 핵심 아이디어를 이해한다.
- 다익스트라 알고리즘과 복잡도
기본버전은 O(N2)
// 인접행렬 방식으로 구하기
const INF = Infinity;
const arr = [
[0, 2, 5, 1, INF, INF],
[2, 0, 3, 2, INF, INF],
[5, 3, 0, 3, 1, 5],
[1, 2, 3, 0, 1, INF],
[INF, INF, 1, 1, 0, 2],
[INF, INF, 5, INF, 2, 0]
];
const isVisit = new Array(6).fill(false);
const getMin = function(vertex){
let min = INF;
let idx = 0;
for(let i=0; i<vertex.length; i++){
if(min > vertex[i] && !isVisit[i]){
min = vertex[i];
idx = i;
}
}
return idx;
}
const dist = function(start){
let v = arr[start-1];
let count = 0;
let end = v.length;
let min = 0;
let startV = v;
isVisit[start-1] = true;
while(count < end){
const idx = getMin(startV);
min += startV[idx];
const next = arr[idx];
for(let i=0; i<v.length; i++){
if(v[i] > next[i]+min && !isVisit[i])
v[i] = next[i]+min;
}
startV = arr[idx];
isVisit[idx] = true;
count++;
}
console.log(v);
}
const main = (function(){
dist(1);
}());
최소힙에 기반한 건 O(변의 개수+ Nlog2N)
const Node = function(vertex, weight=0){
this.vertex = vertex;
this.weight = weight;
this.link = null;
}
const Graph = function(size){
this.graph = Array.from({length: size}, (e,i) => new Node(String.fromCharCode(65+i)));
const insertNode = (v1, v2, w) => {
const v1Node = new Node(v1, w);
const v2Node = new Node(v2, w);
const v1Idx = v1.charCodeAt(0) - 65;
const v2Idx = v2.charCodeAt(0) - 65;
let graph1 = this.graph[v1Idx];
let graph2 = this.graph[v2Idx];
if(graph1.link === null){
graph1.link = v2Node;
}
else{
while(graph1.link !== null){
graph1 = graph1.link;
}
graph1.link = v2Node;
}
if(graph2.link === null){
graph2.link = v1Node;
}
else{
while(graph2.link !== null){
graph2 = graph2.link;
}
graph2.link = v1Node;
}
return;
}
Graph.prototype.insertEdge = function(v1, v2, w){
insertNode(v1, v2, w);
}
Graph.prototype.printGraph = function(){
//간선 그래프 전체 출력
for(let i=0; i<size; i++){
let graph = this.graph[i];
let print = graph.vertex;
while(graph.link !== null){
graph = graph.link;
print += `--[${graph.weight}]--${graph.vertex}`;
}
console.log(print);
}
}
Graph.prototype.getGraph = function(){
return this.graph;
}
}
// 매개변수: 힙, 그래프, 이동거리(가중치), 방문여부
const heapPush = (h, g, move, isVisit) => {
// 다음 그래프가 null이 아닐 때 까지 검사
while(g.link !== null){
g = g.link; // 가중치 0(자기 자신)은 넣지 않는다.
// 방문 유무 검사 하기 위해서
let idx = g.vertex.charCodeAt(0) - 65;
// 방문 했을 경우, heap에 push하지 않는다.
if(!isVisit[idx]){
// g.weight + move: 여태 이동 가중치(move) + 현재 가중치를
// 더해준다. 나머지도 같다
if(!h.length) h.push({v:g.vertex, w:g.weight+move});
else{
if(h[0].w > g.weight){
let temp = h[0];
h[0] = {v:g.vertex, w:g.weight+move};
h.push(temp);
}
else{
h.push({v:g.vertex, w:g.weight+move});
}
}
}
}
}
const heapPop = (h) => {
//최소 힙 구하기!
const item = h[0];
const lastItem = h.pop();
let idx = 0;
if(!h.length) return item;
h[0] = lastItem;
// 자식 노드 유무 확인! 없으면 더 이상 검사 하지 않음!
while(h[idx*2+1] || h[idx*2+2]){
let temp = 0;
// 왼쪽 자식노드 검사
if(h[0].w > h[idx*2+1].w){
temp = h[0];
h[0] = h[idx*2+1];
h[idx*2+1] = temp;
idx = idx*2+1;
}
// 오른쪽 자식노드 검사!
else if(h[idx*2+2] && h[0].w > h[idx*2+2].w){
temp = h[0];
h[0] = h[idx*2+2];
h[idx*2+2] = temp;
idx = idx*2+2;
}
// 왼, 오른쪽 자식노드 둘 다 루트 노드보다 클 경우!
else
idx++;
}
return item;
}
const dijkstra = (start, graph) => {
const size = graph.length; // 정점 개수!
const isVisit = new Array(size).fill(false); // 정점 개수 만큼 방문처리 유무를 검사하기 위한 배열
const dist = []; // 거리 배열
const heap = []; // 힙
let move = 0; // 이동 가중치
let idx = start.charCodeAt(0) - 65; // 현재 인덱스
let g = graph[idx]; // 현재 그래프
heap.push({v:g.vertex, w:g.weight}); // 시작 그래프 노드 push
while(heap.length){
g = heapPop(heap); //최소 힙에서 루트노드(최솟 값) 꺼내기!
idx = g.v.charCodeAt(0) - 65; //방문 유무 검사하기 위한 인덱스
// 방문 되지 않은 정점에 대해서만 작업을 한다.
if(!isVisit[idx]){
isVisit[idx] = true;
move = g.w;
dist[idx] = move;
heapPush(heap, graph[idx], move, isVisit);
}
}
console.log(dist);
}
const main = (function(){
const graph = new Graph(6);
//간선 만들기
graph.insertEdge("A", "B", 1);
graph.insertEdge("A", "C", 9);
graph.insertEdge("B", "C", 10);
graph.insertEdge("B", "D", 2);
graph.insertEdge("C", "D", 5);
graph.insertEdge("C", "E", 1);
graph.insertEdge("D", "E", 1);
graph.insertEdge("E", "F", 2);
//간선 출력
console.log("간선 출력");
graph.printGraph();
//다익스트라 알고리즘 실행!
console.log("\nA의 최소 경로 출력")
dijkstra('A', graph.getGraph());
}());