🚀 **이 문서는 보다 쉽게 이해할 수 있도록 정리되었습니다.**
Dijkstra 알고리즘
최단 경로 알고리즘 – 노드간의 경로를 모두 가는데, 최단 거리 구하기
시작점이 있어야 함. 가중치에 마이너스가 있으면 사용할 수 없음.
1 – 자기 자신 가중치는 0, 자기 자신은 0
PQ에 거리가 가장 짧게 갈 수 있는 노드를 넣고, 거리도 넣고,
우선순위가 다시 정렬될테니 그 중 가장 짧은 거리를 가지는
노드를 빼고, 그 노드에서 다른 위치의 노드로 가는 거리 중
더 짧은게 있다면 갱신 그런 식으로 모든 노드를 방문하면서
짧은 거리를 업데이트
문제의 형태
간선과 노드가 값이 주어지고, 시작점이 주어짐.
이때 node 클래스 만들고,
노드는 dest와 cost로 구성
인접 리스트에 입력
리스트에는 출발지 배열에 도착지와 cost 입력
adjList[출발지].add(new Node(도착지, cost);
adjList[a].add(new Node(b, c));
이렇게 입력을 다 되면
dijkstra(1); // 출발지 정보로 dijkstar 호출
dijkstar(1, -1); // 시작은 현재 어디로 연결될지 모르니 이렇게 호출
“`
static void dijkstra(int start, int dest){
PriorityQueue
// cost 배열을 무한대로 초기화
for(int i = 1; i<= N; i++){
cost[i] = Integer.MAX_VALUE;
}
cost[start] = 0;
PQ.add(new Node(start, 0));
while(!PQ.isEmpty()){
Node now = PQ.poll();
// 목적지 도착
if(now.dest == dest)
break;
// 연결된 간선 탐색
for(Node next : adjList[now.dest]){
// cost가 더 작을 때만 갱신하고 PQ큐에 넣음.
if(cost[next.dest] > next.cost + now.cost){
cost[next.dest] = next.cost + now.cost;
PQ.add(new Node(next.dest , cost[next.dest]));
}
}
}
“`
개발자, 기술사, 삼성, 외국계 IT기업 20년차 기술노트 알렉이 직접 작성한
IT기업 기술 면접을 위한 CS + 면접 노하우 PDF
[https://kmong.com/self-marketing/539751/LUA54VnQsP](https://kmong.com/self-marketing/539751/LUA54VnQsP)
자주 나오는 CS 질문과 답변 그리고 100번 이상 면접관으로 참여하면서 느꼈던
면접자가 알아야 할 팁 13가지 포함
백엔드 개발자를 위한 클라우드 강의, AWS
[https://inf.run/o1NX](https://inf.run/o1NX)
이제는 비전공자도, 일반이도 개발할 수 있다.
ChatGPT를 이용한 누구나 앱개발 with 알렉
[https://inf.run/rpX4](https://inf.run/rpX4)
백엔드 직접 번역한 도서
[https://www.yes24.com/Product/Goods/122536127](https://www.yes24.com/Product/Goods/122536127)
IT기술의 거의 모든 것을 다루는 기술노트with알렉 유투브
[https://www.youtube.com/c/%EA%B8%B0%EC%88%A0%EB%85%B8%ED%8A%B8with%EC%95%8C%EB%A0%89](https://www.youtube.com/c/%EA%B8%B0%EC%88%A0%EB%85%B8%ED%8A%B8with%EC%95%8C%EB%A0%89)