자다가도 일어나서 바로 구현할 수 있어야하는 최단경로를 찾는 다익스트라 알고리즘 파헤치기 1편

1. 최단경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소인 경로 최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 다양한 종류가 있지만 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다 예를 들어 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우", "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우" 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 "노드"로 표현되고, 지점간 연결된 도로는 그래프에서 "간선"으로 표현된다. 2. 다익스트라 최단경로 알고리즘 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 시작 정점에서..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 10. 3.
• textsms

다익스트라 알고리즘 활용하기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하도록 solution ..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 1. 30.
• textsms

다익스트라(dijkstra) 알고리즘

그래프에서 최단경로를 탐색하는 알고리즘 특정 하나의 node에서 다른 모든 node로 가는 최단 경로를 알려줌 link의 가중치가 음수인 경우는 고려하지 않음 하나의 최단 거리를 그 이전까지 구했던 최단 거리 정보를 사용하여 구함 --------------------------------------------------------------------------------------------------------------------- 1. 출발노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 5. 위에서 3.과 4.번을 반복 ----------..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 1. 29.
• textsms