python Dijkstra 정적 길 찾기 알고리즘 실현

알고리즘 소개
디 코스 처 알고리즘 은 그림 이나 그림 이 없 는 단일 소스 의 최 단 경로 문 제 를 광범 위 하 게 검색 하여 해결 하고 알고리즘 은 최종 적 으로 최 단 경로 트 리 를 얻 었 습 니 다.이 알고리즘 은 루트 알고리즘 이나 다른 그림 알고리즘 의 하위 모듈 로 자주 사용 된다.
물론 이 를 물류 처리 에 사용 해 대가 가 가장 적은 운송 방안 을 얻 는 사람 도 있다.
알고리즘 사고
Dijkstra 알고리즘 은 욕심 많은 전략 을 채택 했다.
1.우선,원점 에서 각 정점 까지 의 최 단 거리 와 저장 이 가장 짧 은 경 로 를 찾 은 정점 의 집합 T 를 저장 하기 위해 배열 dis 를 설명 합 니 다.
2.그 다음 에 원점 s 의 경로 가중치 가 0(dis[s]=0)으로 부 여 됩 니 다.만약 에 정점 s 에 직접 도착 할 수 있 는 변(s,m)이 존재 한다 면 dis[m]를 w(s,m)로 설정 하고 모든 다른(s 가 직접 도착 할 수 없 는)정점 의 경로 길 이 를 무한대 로 설정 합 니 다.처음에 집합 T 는 정점 s 만 있 었 다.
3.dis 배열 에서 최소 값 을 선택 하면 이 값 은 원점 s 에서 해당 하 는 정점 까지 의 가장 짧 은 경로 이 고 이 점 을 T 에 넣 으 면 정점 을 완성 합 니 다.
4.새로 추 가 된 정점 이 다른 정점 에 도달 할 수 있 는 지,그리고 이 정점 을 통 해 다른 점 에 도달 하 는 경로 의 길이 가 원점 보다 직접 짧 은 지,그렇다면 이 정점 이 dis 에 있 는 값 을 교체 합 니 다.
5.마지막 으로 dis 에서 최소 값 을 찾 아 상기 동작 을 반복 하고 T 에 그림 의 모든 정점(도착 할 수 있 는)이 포 함 될 때 까지 합 니 다.
알고리즘 그래 픽 데모
현재 그림 은 다음 과 같다.

각 선의 가중치 와 표 지 는 그림 과 같다.
첫 번 째 단계:
dis 배열 과 T 배열 을 만 듭 니 다.
먼저 출발점 A 부터 A 가 직접 도달 할 수 있 는 정점 의 가중치 를 dis 배열 에 기록 하고 직행 할 수 없 는 기록 은 무한대(현재 FFFF 를 사용 하여 무한대)입 니 다.

현재 선택 한 정점 을 배열 T 에 추가 하기:

두 번 째 단계:
dis 배열 에서 T 배열 의 정점 이 아 닌 최소 가중치 의 정점 을 선택 하 십시오.현재 B 정점 으로 선택 하고 B 가 직접 도착 할 수 있 는 정점 의 관련 가중치 와 현재 dis 의 가중치 를 비교 합 니 다.현재 dis 가중치 가 크 면 교체 합 니 다.

B 를 배열 T 에 추가 하기:

세 번 째 단계:
정점 C 순서대로 선택:

C 를 배열 T 에 추가 하기:

네 번 째 단계:
정점 D 순서대로 선택:

D 를 배열 T 에 추가 하기:

다섯 번 째 단계:
정점 E 순서대로 선택:

E 를 배열 T 에 추가 하기:

여섯 번 째 단계:
정점 F 순서대로 선택:

F 를 배열 T 에 추가 하기:

모든 정점 이 T 배열 에 있 기 때문에 알고리즘 이 끝 났 습 니 다.
이렇게 하면 A 점 에서 각 정점 까지 의 최 적 화 를 구 할 수 있다.
A 정점 을 볼 수 있 고 F 정점 까지 갈 수 없습니다.
코드 표시:
(코드 에 999 대표 FFF 사용)

#encoding:utf-8

import copy
"""
      
    
999     
"""
tuG=[[0, 10, 20, 999, 999, 999],
 [999, 0, 999, 20, 70, 999],
 [999, 999, 0, 50, 30, 999],
 [999, 999, 999, 0, 999, 999],
 [999, 999, 999, 10, 0, 999],
 [999, 999, 999, 20, 20, 0]];

tuX = 6;

#               
dis = copy.deepcopy(tuG[0]);

def Dijkstra(G,v0):
 """
    Dijkstra         v0    G             
 INF           
 """
 t = [];
 minv = v0;

 while len(t) <= tuX:
 t.append(minv);
 #           
 for w in range(0, tuX):
  if dis[minv] + G[minv][w] < dis[w]:
  dis[w] = dis[minv] + G[minv][w]

 tmp = 1000;
 for i in range(0, tuX):
  tmpFlag = False;
  for j in range(0, len(t)):
  if i == t[j]:
   tmpFlag = True;
   break;

  if tmpFlag == True:
  continue;

  if tmp > dis[i]:
  tmp = dis[i];
  minv = i;

if __name__ == '__main__': 
 Dijkstra(tuG,0); 
 print dis;

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.