#include #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, X; int d1[1001], d2[1001]; vector go[1001], back[1001], temp[1001]; priority_queue pq; const int INF = 1e9 + 10; void dijkstra(vector* g, int* d, int start){ d[start] = 0; pq.push({d[start], start}); while(!pq.empty()){ auto cur = pq.top(); pq.pop(); if(d[cur.S] != cur.F) continu..

1. 가중치가 1인 무방향 그래프인 경우: BFS로 풀면 최초 방문 위치가 최단 경로가 보장된다.2. 가중치가 있는 방향이 있는 그래프인 경우: 데이크 스트라 알고리즘3. 플로리드 알고리즘(음수 간선도 가능)4. 벨만 포드 알고리즘

[목차] 1. 다익스트라 알고리즘이란? 알고리즘 알고리즘 원리 구현 O(n²) O(ElogE) 알고리즘 분석 의의 다익스트라는 일종의 그리디 이다. 왜? 매 순간 다음 정점을 선택할 때 가중치가 최소인 정점을 선택하기 때문이다. 하지만 그리디의 특성상 부분 최적해가 전체의 최적해를 보장해야 위의 선택이 합리적이라고 할 수 있다. 그렇다면 매 순간 최소 가중치를 가진 정점을 선택하면 항상 최소가 보장될까? 직관 이를 귀류법으로 증명해보자. 반례 [원시적인 다익스트라 알고리즘] #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, st, en; int d[10001];..