도 론, 최 단 경로 문제 총화

위 키 백과 정의 최 단 길:
6 개의 노드 와 7 개의 변 이 있 는 그림
가장 짧 은 경로 문 제 는 도 론 연구 에서 전형 적 인 알고리즘 문제 로 그림 (결점 과 경로 로 구 성 된) 에서 두 결점 간 의 가장 짧 은 경 로 를 찾 는 데 목적 을 둔다.알고리즘 의 구체 적 인 형식 은 다음 과 같다.
질문 - 즉, 시작 점 을 알 고 가장 짧 은 경 로 를 구 하 는 문제 이다.Dijkstra 알고리즘 을 사용 하기에 적합 합 니 다.
종점 의 최 단 경로 문 제 를 확정 하 다. - 출발점 을 정 하 는 문제 와 달리 이 문 제 는 종결 점 을 알 고 가장 짧 은 경 로 를 구 하 는 문제 이다.무방 향도 에서 이 문 제 는 기점 을 확정 하 는 문제 와 완전히 같 고 유방 향도 에서 이 문 제 는 모든 경로 방향 을 반전 시 키 는 기점 을 확정 하 는 문제 와 같다.
출발점 종점 의 최 단 경로 문 제 를 확정 하 다. - 즉, 출발점 과 종점 을 알 고 두 결점 사이 의 가장 짧 은 경 로 를 구 하 는 것 이다.
전역 최 단 경로 문제 - 그림 의 모든 최 단 경 로 를 구하 십시오.Floyd - Warshall 알고리즘 을 사용 하기에 적합 합 니 다.
최 단 경로 문 제 를 해결 하 는 알고리즘 을 '최 단 경로 알고리즘' 이 라 고 부 르 고 '경로 알고리즘' 이 라 고 부 르 기도 한다.가장 많이 사용 되 는 경로 알고리즘 은 다음 과 같 습 니 다.
Dijkstra 알고리즘 A * 알고리즘 Bellman - ford 알고리즘 SPFA 알고리즘 (Bellman - ford 알고리즘 개선 버 전) Floyd - Warshall 알고리즘 Johnson 알고리즘 Bi - Direction BFS 알고리즘 1. floyd 알고리즘 (프로 이 드) (n ^ 3 복잡 도)
기본 사상: 집합 S 의 초기 상 태 를 비 운 다음 에 0, 1 을 순서대로 설정 합 니 다.n - 1 지정 가입, 동시에 d [i] [j] 로 i 에서 j 까지 저장 하고 S 의 지정 한 가장 짧 은 경로 만 거 칩 니 다. 초기 에 d [i] [j] = A [i] [j] 중간 에 그 어떠한 노드 도 거치 지 않 고 S 에 노드 를 순서대로 삽입 하고 다음 과 같이 d (k) [i] [j] = min {를 업데이트 합 니 다. d(k-1)[i][j] ,  d(k-1)[i][k]+d(k-1)[k][j]  } 또한 2 차원 배열 path 를 사용 하여 최 단 경 로 를 표시 할 수 있 습 니 다. path [i] [j] 는 지정 i 에서 j 까지 의 최 단 경 로 를 제시 합 니 다. 지정 i 의 앞 정점 코드 는 상당히 간단 하고 가장 쉬 운 실현 방법 을 제시 합 니 다.

for (k = 0;k < n;k++)
for (i = 0;i < n;i++)
for (j = 0;j < n;j++)
{
	if (d[i][k] + d[k][j] < d[i][j])
	{
		d[i][j] = d[i][k] + d[k][j];
		path[i][j] = path[k][j];
	}
}

전달 을 통 해 경 로 를 알 수 있 습 니 다.
2. dijstra (디 제 스 트 라 알고리즘) 알고리즘
단일 소스 최 단 로 문 제 는 먼저 소스 에 가입 하고 표 한 장 을 유지 하여 현재 소스 의 최 단 거 리 를 저장 하고 가장 작은 가입 을 선택 한 다음 에 표를 업데이트 하고 목적지 가 소스 에 있 을 때 까지 계속 가입 합 니 다. 정 변 권 에 만 적용 되 는 경우 에 만 우 리 는 임의로 가입 한 점 이 이 점 에서 원 하 는 거 리 를 찾 았 음 을 보증 할 수 있 기 때 문 입 니 다.
 
3. bellman - ford 알고리즘
 
최 우성 원리
최 우수 원리 소개 및 간단 한 증명:http://blog.csdn.net/liguanxing/article/details/7401798
이것 은 가장 좋 은 원리 의 직접적인 응용 이 고 알고리즘 은 다음 과 같은 사실 을 바탕 으로 한다.
만약 에 가장 짧 은 길이 존재 한다 면 각 정점 은 최대 한 번 지나 가기 때문에 n - 1 개의 변 을 초과 하지 않 는 다.
길이 가 k 인 길 이 는 k - 1 인 길 에 한 변 을 더 해서 얻 을 수 있 습 니 다.
최 우성 원리 에서 길이 가 1, 2,..., k - 1 인 최 단 로 를 차례대로 고려 해 야 한다.
 
적용 조건 & 범위
단일 소스 최 단 경로 (원점 s 에서 다른 모든 정점 v);
유방 향도 & 무방 향도 (무방 향도 (u, v), (v, u) 는 변 집 E 에 속 하 는 유방 향도 로 볼 수 있다).
변 권 은 마이너스 가 될 수 있 습 니 다 (만약 마이너스 회로 출력 오류 알림 이 있 으 면).
 계차 제약 시스템  
 
알고리즘 설명
 1) 각 변 에 | V | - 1 회 Relax 작업 을 진행 합 니 다.
 2) 만약 (u, v) 8712 ° E 가 존재 한다 면 dis [u] + w < dis [v] 는 마이너스 회로 가 존재 합 니 다. 그렇지 않 으 면 dis [v] 는 s 에서 v 까지 의 최 단 거리 이 고 pre [v] 는 선구자 입 니 다.  
 

for i:=1 to |V|-1 do //  |v|-1        
    for    (u,v)∈E do   
        Relax(u,v,w);
for   (u,v)∈E do //         
    if dis[u]+w<dis[v] 
        Then Exit(False)

알고리즘 시간 복잡 도 O (VE). 알고리즘 이 간단 하고 적용 범위 가 넓 기 때문에 복잡 도가 약간 높 지만 실 용적 인 알고리즘 이 라 고 할 수 있 습 니 다.  
개선 과 최적화  n - 1 회 순환 하기 전에 꽉 끼 지 않 은 것 을 발견 하면 즉시 종료 할 수 있 습 니 다.
 
 
4. spfa 알고리즘
SPFA (Shortest Path Faster Algorithm) 는 Bellman - ford 알고리즘 의 한 대기 열 로 이 루어 져 불필요 한 불필요 한 계산 을 줄 였 습 니 다. O (kE) 의 시간 복잡 도 에서 원점 에서 다른 모든 점 까지 의 최 단 경 로 를 구 할 수 있 으 며, 마이너스 변 을 처리 할 수 있 습 니 다.
 
 
알고리즘 흐름  
SPFA 가 Bellman - ford 알고리즘 을 최적화 하 는 관건 은 앞의 이완 에서 거리 평가 치 를 바 꾼 점 만 이 인접 점 의 거리 평가 치 변 화 를 일 으 킬 수 있다 는 것 을 의식 하 는 것 이다. 따라서 알고리즘 은 대체적으로 하나의 대기 열 로 유지 하 는 것 이다. 즉, 먼저 나 온 대기 열 로 성공 적 으로 느슨 해진 정점 을 저장 하 는 것 이다. 초기 에 원점 s 가 들 어 왔 을 때팀. 대기 열 이 비어 있 지 않 을 때, 팀 의 첫 번 째 정점 을 꺼 내 인접 점 을 이완 시 킵 니 다. 만약 인접 점 이 이완 에 성공 하고, 이 인접 점 이 대기 열 에 없 으 면, 그것 을 팀 에 넣 습 니 다. 제 한 된 이완 작업 을 거 친 후, 대기 열 은 비어 있 고, 알고리즘 은 끝 납 니 다. SPFA 알고리즘 의 실현 을 위해 서 는 먼저 나 온 대기 열 을 사용 해 야 합 니 다. queue 대기 열 에 있 는 태그 배열 mark 를 표시 할 지 여 부 를 표시 합 니 다. 특정한 정점 의 인접 점 을 쉽게 찾기 위해 그림 은 임계 표 로 저장 합 니 다.

Procedure SPFA;
 
Begin
   initialize-single-source(G,s);
   initialize-queue(Q);
   enqueue(Q,s);
   while not empty(Q) do begin
      u:=dequeue(Q);
      for each v∈adj[u] do begin
         tmp:=d[v];
         relax(u,v);
         if (tmp<>d[v]) and (not v in Q) then enqueue(Q,v);
         end;
      end;
End;

주의: spfa 알고리즘 은 마이너스 링 이 존재 하지 않 는 상황 에서 만 정상적으로 끝 날 수 있 습 니 다. 만약 에 마이너스 링 이 존재 한다 면
항상 꼭지점 이 팀 에 들 어 오고 나 오 며, 대기 열 이 비어 있 을 수 없 는 상황 에서 SPFA 가 정상적으로 끝 날 수 없습니다. 하나의 변 수 를 추가 하여 각 꼭지점 이 대기 열 에 들 어 가 는 횟수 를 표시 할 수 있 습 니 다. | v | 보다 크 면 마이너스 링 이 존재 한 다 는 것 을 설명 할 수 있 습 니 다.