노는 게 제일 좋아

다익스트라가 가중치가 양수일 때만 최단거리를 찾는 알고리즘이라면 이 벨만-포드 알고리즘은 음수의 가중치도 계산한다고 보면 되겠다. 어렵지 않고.. 그냥 다익스트라를 정점개수-1만큼 돌린다고 생각하면 된다. **일반적으로 음수의 가중치는 나오지 않으나 간선을 돌아감에도 비용이 줄어든다는 것은 예를 들어 신호가 x만큼 증폭되는 증폭기가 있다고 했을 때 증폭기가 우리가 갈 노드의 수를 줄여준다고도 볼 수 있겠다. 알아보자 다익스트라가 양수가중치만 있을 때 사용하는 알고리즘이라면 벨만 포드 알고리즘은 음수 가중치가 존재해야만 의미있는 알고리즘이다. 알아보자 #include #include #include using namespace std; //간선을 표현할 Edge typedef struct Edge { in..

한 번 갔던 간선에 대해 다시 갈 수 있으므로 연결해줄 때 양방향으로 연결해줘야 했다. 남들은 잘보이지만 나는 이것만 30분 넘게.. 걸렸다. 그리고 어차피 최단경로 = 최단경로 + 최단경로라고 생각해도 된다. https://www.acmicpc.net/problem/1504 #맞는 풀이 #include #include #include #include #include #include #define MAX 803 #define INF INT_MAX using namespace std; int N, E; vector adj[MAX]; //인접행렬 long long dist[MAX]; long long dist1[MAX]; //v1을 위한 long long dist2[MAX]; //v2를 위한 int v1, ..

다익스트라의 개념이 조금 더 나아간 것이다. 최단거리로 갱신했을 때는 해당 경로가 정해진다는 것을 기록하면 되는 문제다. https://www.acmicpc.net/problem/11779 #맞는 풀이 #include #include #include #include #include #include #define MAX 1002 #define INF 987654321 using namespace std; int st, ed; int N, M; int dist[MAX]; vector adj[MAX]; int path[MAX]; void dijkstra() { dist[st] = 0; priority_queue heap; heap.push({ dist[st], st }); while (!heap.empty()..

다익스트라 알고리즘 또 까먹었다. 오늘은 3문제 정도 풀어봐야겠다. https://www.acmicpc.net/problem/1916 #맞는 풀이 #include #include #include #include #include #define MAX 1001 // 1000개 정도면 인접행렬 만들만하다. #define INF 987654321 //적당히 큰 숫자여야한다. using namespace std; int N; //도시 수 int M; //버스 수 int st, ed; //시작노드, 목표노드 vector adj[MAX]; //벡터를 넣는 배열 {거리, 노드} int dist[MAX]; //최소거리 테이블 void dijkstra(){ dist[st] = 0; //전역으로 시작노드를 받음. prior..

우선 이 알고리즘을 쓰기 위해서는 몇가지 조건이 필요하다. 1. 각 간선에 대한 가중치가 음수여선 안된다. -> 양수여야만 한다. 2. 단일 시작점에 대한 최단 경로이다. -> 해당 시작점에 대해서만 최단경로고 다른 vertex는 다시 돌려야 한다. 3. 프림의 MST 알고리즘과 유사한 형태다. -> 프림 알고리즘은 경계로부터의 최소 거리를 정점의 거리 값으로 설정 -> 다익스트라에서는 시작 정점으로부터 각 정점까지의 전체거리 사용 -> 다익스트라에서는 목적 정점만 파악하면 종료 아무튼 조금 다르다. 우선 기본적으로 해야 할 것들을 알아보자 1. 모든 정점에 대해서 거리 값을 무한대로 초기화한다 -> 계산하지 않았음을 의미한다. 2. 시작정점 자기자신과의 거리는 0이므로 0으로 설정한다. 3. 모든 거리..