HDU - 2544 - 최 단 로 (가장 기본 적 인 단일 소스 최 단 로 문제!! dijkstra + floyd + SPFA)

최 단 로
Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 34617    Accepted Submission(s): 15001
Problem Description
매년 학교 경기 에서 결승전 에 진출 하 는 모든 학우 들 은 매우 아름 다운 t - shirt 를 받는다.하지만 우리 스 태 프 들 이 수백 벌 에 달 하 는 옷 을 상점 에서 경기장 으로 옮 길 때마다 매우 피곤 하 다!그래서 지금 그들 은 가장 짧 은 상점 에서 경기장 까지 의 노선 을 찾 으 려 고 하 는데, 당신 은 그들 을 도와 줄 수 있 습 니까?
 
Input
여러 그룹의 데 이 터 를 입력 하 십시오.각 조 의 데이터 첫 줄 은 두 개의 정수 N, M (N & lt; 100, M & gt; = 10000) 이 고 N 은 청 두 의 거리 에 몇 개의 길목 이 있 고 1 로 표 시 된 길목 은 상점 소재지 이 며 N 으로 표 시 된 길목 은 경기장 소재지 이 며 M 은 청 두에 몇 개의 길이 있다 고 표시 한다.N = M = 0 은 입력 이 끝 났 음 을 나타 낸다.다음 M 줄 은 각 줄 에 3 개의 정수 A, B, C (1 & lt; = A, B & gt; = N, 1 & gt; = C & gt; = 1000) 를 포함 하여 길목 A 와 길목 B 사이 에 길이 있다 는 것 을 나타 내 고 우리 직원 들 은 C 분 의 시간 이 이 길 을 걸 어야 한다.
적어도 한 개의 상점 이 경기장 으로 가 는 노선 을 입력 하 세 요.
 
Output
각 조 의 수입 에 대해 한 줄 을 수출 하 는 것 은 직원 들 이 상점 에서 경기장 으로 가 는 가장 짧 은 시간 을 나타 낸다.
 
Sample Input

   
   
   
   

    
    
    
    2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
2
   
   
   
   

 
Source
UESTC 6th Programming Contest Online
 
dijkstra:
경로 길이 증가 순서에 따라 알고리즘 생 성:
정점 집합 V 를 두 그룹 으로 나 누 기:
(1) S: 이미 구 한 정점 의 집합 (초기 에는 원점 V0 만 포함)
(2) V - S = T: 아직 정 해 지지 않 은 정점 집합
T 의 정점 을 증가 하 는 순서에 따라 S 에 추가 하고 보증 합 니 다.
(1) 원점 V0 에서 S 까지 다른 각 정점 의 길 이 는 V0 에서 T 까지 그 어떠한 정점 의 최 단 경로 길이 보다 크 지 않다.
(2) 정점 마다 거리 값 대응
S 중 정점: V0 에서 이 정점 까지 의 길이
T 중 정점: V0 에서 이 정점 까지 S 중 정점 을 중간 정점 으로 하 는 가장 짧 은 경로 길이 만 포함 합 니 다.
근거: V0 에서 T 까지 의 정점 Vk 또는 V0 에서 Vk 까지 의 직접 경로 의 가중치 를 증명 할 수 있 습 니 다.또는 V0 경 S 에서 Vk 까지 의 경로 가중치 의 합
(반증 법 은 증명 할 수 있다)
최 단 경로 절차 구하 기
알고리즘 절 차 는 다음 과 같다.
G={V,E}
1. 초기 시령 S = {V0}, T = V - S = {나머지 정점}, T 의 정점 에 대응 하 는 거리 값
< V0, vi >, d (V0, Vi) 가 존재 하면 < V0, vi > 호의 가중치 입 니 다.
만약 존재 하지 않 는 다 면 < V0, vi >, d (V0, Vi) 는 표시 이다.
2. T 에서 S 의 정점 과 관련 이 있 고 가중치 가 가장 작은 정점 W 를 선택 하여 S 에 넣는다.
3. 나머지 T 중 정점 의 거리 값 을 수정 합 니 다. W 를 중간 정점 으로 추가 하면 V0 에서 Vi 까지 의 거리 값 이 짧 아 지면 이 거리 값 을 수정 합 니 다.
S 에 모든 정점, 즉 W = Vi 가 포 함 될 때 까지 상기 절 차 를 2, 3 반복 합 니 다.
dijkstra 는 확실히 최소 생 성 트 리 의 prim 과 비슷 합 니 다!!
dijkstra + floyd + SPFA (프로필):
Bellman-Ford：
단원 최 단 로 를 구하 면 마이너스 회로 (있 으 면 최 단 로 는 존재 하지 않 음) 가 있 는 지 판단 할 수 있 고 실효 성 이 좋 으 며 시간 복잡 도 O (VE) 가 있다.
Bellman - ford 알고리즘 은 단원 의 가장 짧 은 경로 문 제 를 푸 는 알고리즘 이다.
      단원 점 의 가장 짧 은 경로 문 제 는 다음 과 같다. 가중 권 을 지정 하면 그림 G 와 원점 s 가 있 고 그림 G 의 임의의 v 에 대해 s 에서 v 까지 의 가장 짧 은 경 로 를 구한다.
      Dijkstra 알고리즘 과 달리 Bellman - ford 알고리즘 에서 변 의 가중치 가 마이너스 가 될 수 있 습 니 다.      우리 가 그림 에서 하나의 순환 로 (즉, v 에서 출발 하여 몇 개의 점 을 거 친 후에 다시 v 로 돌아 갈 수 있다) 를 찾 을 수 있 고 이 순환 로 에서 모든 변 의 가중치 의 합 이 마이너스 라 고 구상 할 수 있다.그러면 이 순환 도 로 를 통 해 순환 도로 중 임의의 두 점 의 가장 짧 은 경 로 는 무한 하고 작 아 질 수 있다.만약 이 네 거 티 브 순환 로 를 처리 하지 않 는 다 면 프로그램 은 영원히 실 행 될 것 이다.벨 맨 - ford 알고리즘 은 이런 마이너스 순환 로 를 분별 하 는 능력 을 가지 고 있다.
Dijkstra：
단원, 무 부권 의 최 단 로 를 구하 다.실효 성 이 좋 고 시간 복잡 도 는 O (V * V + E) 이다.원점 에 도달 하면 O (V * lgV + E * lgV) = > O (E * lgV).      희소 한 그림 의 경우 이때 E = V * V / lgV 이기 때문에 알고리즘 의 시간 복잡 도 는 O（V^2）  。피 보 나치 더미 가 우선 대기 열 을 만 들 면 알고리즘 시간 복잡 도 는 O (V * lgV + E) 입 니 다. 
Floyd：
다 원, 무 마이너스 변 의 최 단 로 를 구하 다.행렬 로 그림 을 기록 하 다.실효 성 이 떨 어 지고 시간 복잡 도 O (V ^ 3).       Floyd - Warshall 알고리즘 (Floyd - Warshall algorithm) 은 임의의 두 점 간 의 가장 짧 은 경 로 를 해결 하 는 알고리즘 으로 그림 이나 마이너스 권 이 있 는 가장 짧 은 경로 문 제 를 정확하게 처리 할 수 있 습 니 다.
Floyd - Warshall 알고리즘 의 시간 복잡 도 는 O (N ^ 3) 이 고 공간 복잡 도 는 O (N ^ 2) 입 니 다.
      Floyd - Warshall 의 원 리 는 동적 계획 이다. Di, j, k 를 i 에서 j 까지 의 집합 중의 노드 만 중간 노드 의 가장 짧 은 경로 의 길이 로 설정 하 는 것 이다.가장 짧 은 경로 가 점 k 를 지나 면 Di, j, k = Di, k, k - 1 + Dk, j, k - 1;  가장 짧 은 경로 가 점 k 를 거치 지 않 으 면 Di, j, k = Di, j, k - 1.  따라서 Di, j, k = min (Di, k, k - 1 + Dk, j, k - 1, Di, j, k - 1).
      실제 알고리즘 에서 공간 을 절약 하기 위해 원래 공간 에서 직접 교체 할 수 있 고 이런 공간 은 2 차원 으로 내 려 갈 수 있다.Floyd - Warshall 알고리즘 에 대한 설명 은 다음 과 같 습 니 다. for k ← 1 to n do  for i ← 1 to n do     for j ← 1 to n do       if (Di,k + Dk,j < Di,j) then         Di,j ← Di,k + Dk,j; 그 중에서 Di, j 는 점 i 에서 점 j 까지 의 대 가 를 나타 내 는데 Di, j 는 두 점 사이 에 아무런 연결 이 없다 는 것 을 나타 낸다.
나중에 벨 맨 - 포드 의 대열 최적화, SPFA ( Shortest Path Faster Algorithm   ）。
SPFA：
Bellman - ford 의 대기 열 최적화 입 니 다. 실효 성 이 상대 적 으로 좋 고 시간 복잡 도 O (kE) 입 니 다. (k < < V).
Bellman - ford 알고리즘 과 유사 합 니 다. SPFA 알고리즘 은 일련의 이완 작업 을 통 해 특정한 노드 에서 출발 하여 그림 에 있 는 다른 모든 노드 의 가장 짧 은 경 로 를 얻 을 수 있 습 니 다. 다른 것 은 SPFA 알고리즘 이 통과 한 것 입 니 다. 대기 열 유지 ，한 노드 의 현재 최 단 경로 가 업 데 이 트 된 후에 다른 노드 를 바로 업데이트 할 필요 가 없어 서 중복 되 는 조작 횟수 를 크게 줄 였 다.
      SPFA 알고리즘 은 마이너스 변 권 이 존재 하 는 그림 에 사용 할 수 있 는데 이것 은 dijkstra 알고리즘 과 다르다.
Dijkstra 알고리즘 과 Bellman - ford 알고리즘 도. 서로 다른 SPFA 의 알고리즘 시간 효율 은 불안정 하 다. 즉, 서로 다른 그림 에 필요 한 시간 에 큰 차이 가 있다 는 것 이다.
      가장 좋 은 상황 에서 모든 노드 가 한 번 만 가입 하면 알고리즘 은 실제 적 으로 넓 은 범위 로 옮 겨 다 니 며 시간 복잡 도 는 O (E) 에 불과 합 니 다. 다른 한편, 이러한 예 가 존재 하여 모든 노드 가 가입 (V - 1) 되 었 습 니 다. 이때 알고리즘 은 Bellman - ford 알고리즘 으로 퇴화 되 었 고 그 시간 복잡 도 는 O (VE) 입 니 다.
      SPFA 알고리즘 은 음 변 권 도 에서 Bellman - ford 알고리즘 을 완전히 대체 할 수 있 으 며, 희소 도 에서 도 양호 합 니 다. 그러나 비 음 변 권 도 에 서 는 최 악의 상황 을 피하 기 위해 효율 적 이 고 안정 적 인 Dijkstra 알고리즘 과 최 적 화 된 버 전 을 사용 합 니 다. 일반적인 SPFA 알고리즘 은 격자 그림 에서 의 표현 이 만 족 스 럽 지 못 합 니 다.
AC 코드 1 (dijkstra):

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x7f7f7f7f
using namespace std;

const int N = 105;
int map[N][N], vis[N], dis[N];
int n, m;

void dijk()
{
	for(int i=1; i<=n; i++) dis[i] = INF;
	dis[1] = 0;
	for(int i=1; i<=n; i++)
	{
		int min = INF, pos;
		for(int j = 1; j<=n; j++)
			if(!vis[j] && dis[j] < min) 
				min = dis[pos = j];
		vis[pos] = 1;
		for(int j=1; j<=n; j++)
			if(!vis[j] && dis[pos] + map[pos][j] < dis[j])
				dis[j] = dis[pos] + map[pos][j];
	}
}

int main()
{
	while(scanf("%d %d", &n, &m) == 2 && n||m)
	{
		memset(vis, 0, sizeof(vis));
		memset(map, 0x7f, sizeof(map));
		while(m--)
		{
			int x, y, w;
			scanf("%d %d %d", &x, &y, &w);
			if(w < map[x][y]) map[x][y] = map[y][x] = w;
		}
		dijk();
		printf("%d
", dis[n]);
	}
	return 0;
}

AC 코드 2 (floyd):

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f			//       ，   0x7f7f7f7f            
using namespace std;

const int MAX = 105;
int map[MAX][MAX];
int n, m;

void floyd()
{
	for(int k=1; k <= n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(map[i][k] + map[k][j] < map[i][j])		//        
					map[i][j] = map[i][k] + map[k][j];
}

int main()
{
	while(scanf("%d %d", &n, &m) == 2 && n||m)
	{
		memset(map, 0x3f, sizeof(map));
		while(m--)
		{
			int x, y, w;
			scanf("%d %d %d", &x, &y, &w);
			if(w < map[x][y]) map[x][y] = map[y][x] = w;
		}
		floyd();
		printf("%d
", map[1][n]);
	}
	return 0;
} 

AC 코드 3 (SPFA):

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

const int MAX = 105;
int map[MAX][MAX], dis[MAX], vis[MAX];
int n, m;

void spfa(int s)
{
	int pos;
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	while(!q.empty())
	{
		pos = q.front(); q.pop();
		vis[pos] = 0;
		for(int i=1; i<=n; i++)
		{
			if(dis[pos] + map[pos][i] < dis[i])
			{
				dis[i] = dis[pos] + map[pos][i];
				if(vis[i] == 0)
				{
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}
}

int main()
{
	while(scanf("%d %d", &n, &m)==2 && n||m)
	{
		memset(vis, 0, sizeof(vis));
		memset(map, 0x3f, sizeof(map));
		memset(dis, 0x3f, sizeof(dis));
		for(int i=1; i <= n; i++) map[i][i] = 0;
		while(m--)
		{
			int x, y, w;
			scanf("%d %d %d", &x, &y, &w);
			if(w < map[x][y]) map[x][y] = map[y][x] = w;
		}
		spfa(1);
		printf("%d
", dis[n]);
	}
	return 0;
}