[Algorithm] 다익스트라(Dijkstra) 알고리즘 with c#
근 몇 년 동안 이직을 2번이나 하느라,, 굉장히 바쁜 하루하루를 살았어요
그러다 보니 블로그를 거의 안 들어오게 되었고
정신 차려보니...23년5월..
다시 정신을 부여잡고 내가 배우고 공부한 것을 작성해 보기!
1. 다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프에서 최단 경로를 찾기 위해 사용되는 알고리즘이다.
특정 출발점부터 다른 정점까지의 최단 경로를 구하는 문제를 해결하는 데에 적용된다.
다익스트라 알고리즘은 각 정점까지의 최단 거리를 점진적으로 계산하며, 그리디 알고리즘의 한 형태이다.
2. 다익스트라(Dijkstra) 알고리즘 활용분야
다익스트라 알고리즘은 다양한 분야에서 활용되는데, 대표적으로
- 길 찾기 애플리케이션 : 지도 서비스나 네비게이션 시스템에서 출발지와 목적지 사이의 최단경로
- 네트워크 라우팅 : 패킷 스위칭 네트워크에서 데이터 패킷을 최적 경로를 결정할 때
- 자원 할당 : 자원을 효율적으로 할당하기 위해 다익스트라 알고리즘 사용
- DNA 시퀀싱 : DNA 시퀀싱 데이터에서 유전자 간의 거리를 계산할 때
위와 같은 다양한 분야에서 다익스트라 알고리즘이 사용되며, 최단 경로 문제를 해결하는 데에
유용한 도구로 활용된다!
3. 다익스트라(Dijkstra) 알고리즘 예제
그럼 이제 쉬운 예제로 한번 공부해 보고 예제를 만들어 볼까요
위 그래프를 보면 노드 간의 연결된 선을 간선이라고 하는데 간선들이 연결되어 있고
그리고 그 간선들마다 거리값이 있는 것을 알 수 있다.
위와 같은 그래프가 있을 때 각 정점(노드)에서 특정(노드)으로의 거리를 2차원 배열 형태로 처리해 줄 수 있다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 2 | 5 | 1 | INF | INF |
| 2 | 2 | 0 | 3 | 2 | INF | INF |
| 3 | 5 | 3 | 0 | 3 | 1 | 5 |
| 4 | 1 | 2 | 3 | 0 | 1 | INF |
| 5 | INF | INF | 5 | 1 | 0 | 2 |
| 6 | INF | INF | 5 | INF | 2 | 0 |
(INF는 간선이 가질 수 있는 거리 비용의 최댓값보다 항상 큰 값이라고 생각하면 된다.)
그렇다면 위의 데이터를 바탕으로, 1번 노드에서 6번 노드로 가는 최단거리를 구한다면?
1. 출발 노드와 도착 노드 설정
- 출발 노드 : 1
- 도착 노드 : 6
2. 최단거리 테이블 초기화
1번 노드에서 각 정점의 최소 비용을 테이블로 적성해 준다.
1번 노드는 현재 자기 자신이니 방문처리를 해놓는다.
3. 현재 위치 안 인접 노드 중 방문하지 않은 노드를 구별하고, 가장 거리가 짧은 노드 선택(선택한 노드는 방문처리하기)
- 현재 위치: 1
- 방문하지 않은 노드 중 가장 거리가 짧은 노드 선택 : 4
4. 해당 노드를 거쳐서 다른 노드를 넘어가는 간선 비용 계산하여 테이블을 업데이트한다.
- 해당 노드 : 4
노드 2 : 1번 노드 -> 4번 노드 -> 2번 노드 = 1 + 2 = 3
1번 노드에서 2번 노드로 직접 가는 비용 2 보다 4번을 통해 거쳐가는 비용이 3으로 더 크기 때문에
최소 비용을 그대로 유지하기
노드 3 : 1번 노드 -> 4번 노드 -> 3번 노드 = 1 + 3 = 4
1번 노드에서 3번 노드로 직접 가는 비용 5 보다 4번을 통해 거쳐가는 비용이 4이므로 더 작기 때문에
최소 비용을 업데이트해 주기
노드 5 : 1번 노드 -> 4번 노드 -> 5번 노드 = 1 + 1 = 2
1번 노드에서 5번 노드로 최소 비용은 INF(무한)이기 때문에
최소 비용을 업데이트해 주기
5. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택
(선택한 노드는 방문 처리)
- 현재 위치 : 4
- (방문하지 않은 노드 중) 가장 짧은 노드 선택 : 2
6. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산하여 테이블을 업데이트
- 해당 노드 : 2
- 노드 3 : 1번 노드 -> 2번 노드 -> 3번 노드 2 + 3 = 5
1번 노드에서 직접 가는 비용이 5이므로
최소비용을 그대로 유지
7. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 가장 거리가 짧은 노드 선택
(선택한 노드는 방문처리)
- 현재 노드 2:
- 해당 노드 5
8. 똑같이 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산하여 테이블 업데이트
- 해당 노드 5
- 노드 3 : 1번 노드 ->4번 노드 -> 5번 노드 ->3번 노드 1 + 1+ 1 = 3
1번 노드에서 직접 가는 비용이 5이므로
최소비용을 업데이트
- 노드 6 : 1번 노드 -> 4번 노드 -> 5번 노드 -> 6번 노드 1 + 1 + 2 = 4
1번노드에서 6번 노드까지 가는 비용은 INF이기 때문에
최소비용을 업데이트
9. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택
(선택한 노드는 방문 처리)
-현재 위치 :5
-방문하지 않은 노드중 가장 짧은 노드 : 3
10. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 업데이트
-해당 노드 :3
- 방문하지 않은 노드 중 연경 된 노드 : 6
- 노드 6 : 노드 3까지 최소비용 1번 노드 -> 4번 노드 -> 5번 노드 -3번 노드 = 3 + 5 = 8
노드 6까지 가는 최소 비용 4보다 크기 때문에
최소 비용을 그대로 유지
11. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택
(선택한 노드는 방문 처리)
- 해당 노드 : 6
-연결된 노드 : X
더 이상 방문할 노드가 없으므로 최종 배열은 위와 같이 형성이 된다.
노드 1에서 노드 6으로 가는 최소 비용은 4가 나오는 것을 알 수 있다.
4. 다익스트라(Dijkstra) 알고리즘 동작 단
① 출발 노드와 도착 노드를 설정한다.
② '최단 거리 테이블'을 초기화한다.
③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
④ 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.
⑤ ③~④의 과정을 반복한다.
5. 다익스트라(Dijkstra) 알고리즘 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp1
{
class dijkstra
{
static public int number = 6; //정점의 개수
static public int INF = 1000000000;
static public bool[] v = new bool[6]; //방문한 노드
static public int[] d = new int[6]; // 최단거리 // 전체 그래프 초기화
static public int[,] a = new int[6, 6]{
{ 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}
};
static void Main(string[] args)
{
dikstra1(0);
for(int i=0;i<number; i++)
{
Console.WriteLine(d[i]);
}
}
static public int getSmallIndex()
{
int min = INF;
int index = 0;
for(int i =0; i< number; i++)
{
if(d[i] < min && !v[i])
{
min = d[i];
index = i;
}
}
return index;
}
//다익스트라 수행 함수
static public void dikstra1(int start)
{
for(int i=0; i< number; i++)
{
d[i] = a[start,i];
}
v[start] = true;
for(int i=0; i< number-2; i++)
{
int current = getSmallIndex();
v[current] = true;
for(int j=0; j<6; j++)
{
if(!v[j])
if (d[current] + a[current, j] < d[j])
{
d[j] = d[current] + a[current, j];
}
}
}
}
}
}5. 다익스트라(Dijkstra) 알고리즘 심화
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace example
{
public class Dijkstra
{
private int V; // 정점 개수
private List<(int, int)>[] adjList; // 인접 리스트
public Dijkstra(int vertices)
{
V = vertices;
adjList = new List<(int, int)>[V];
for (int i = 0; i < V; i++)
{
adjList[i] = new List<(int, int)>();
}
}
public void AddEdge(int source, int destination, int weight)
{
adjList[source].Add((destination, weight));
adjList[destination].Add((source, weight));
}
public List<int> FindShortestPath(int source, int destination)
{
int[] distance = new int[V];
int[] previous = new int[V];
SortedSet<(int, int)> pq = new SortedSet<(int, int)>(Comparer<(int, int)>.Create((a, b) => a.Item2.CompareTo(b.Item2)));
for (int i = 0; i < V; i++)
{
distance[i] = int.MaxValue;
previous[i] = -1;
}
distance[source] = 0;
pq.Add((source, 0));
while (pq.Count > 0)
{
(int vertex, int dist) = pq.Min;
pq.Remove(pq.Min);
if (dist > distance[vertex])
{
continue;
}
foreach ((int neighbor, int weight) in adjList[vertex])
{
int newDist = distance[vertex] + weight;
if (newDist < distance[neighbor])
{
distance[neighbor] = newDist;
previous[neighbor] = vertex;
pq.Add((neighbor, newDist));
}
}
}
List<int> shortestPath = new List<int>();
int current = destination;
while (current != -1)
{
shortestPath.Insert(0, current);
current = previous[current];
}
return shortestPath;
}
}
class heapuse_dikstra
{
static void Main(string[] args)
{
int vertices = 6;
Dijkstra dijkstra = new Dijkstra(vertices);
dijkstra.AddEdge(0, 1, 5);
dijkstra.AddEdge(0, 2, 3);
dijkstra.AddEdge(1, 3, 2);
dijkstra.AddEdge(2, 1, 1);
dijkstra.AddEdge(2, 3, 1);
dijkstra.AddEdge(3, 4, 4);
dijkstra.AddEdge(2, 4, 7);
dijkstra.AddEdge(4, 5, 6);
int source = 0;
int destination = 5;
List<int> shortestPath = dijkstra.FindShortestPath(source, destination);
Console.WriteLine("최단 경로의 거리: " + shortestPath.Count);
Console.Write("최단 경로: ");
foreach (int vertex in shortestPath)
{
Console.Write(vertex + " ");
}
}
}
}