상용 데이터 구조의 프로 이 드 알고리즘

프로 이 드 알고리즘 은 그림 의 정점 까지 의 가장 짧 은 경로 문 제 를 해결 하 는 것 이다.보통 한 쌍 의 정점 사이 의 최소 경로 에 적용 된다.

void Floyd(Mgraph g,path[maxsize]){
	int A[maxsize][maxsize];
	for(int i=0;iA[i][k]+A[j][k]){
					A[i][j]=A[i][k]+A[j][k];
					
				}
			}
		}
	}
		
	
}

그 관건 적 인 절 차 는 삼중 순환 이다.가장 바깥 의 순환 은 전체 그림 의 정점 을 옮 겨 다 니 는 것 입 니 다. 각 정점 에서 가장 요구 하 는 두 노드 의 중간 노드 를 배열 에 업데이트 하고 마지막 까지 배열 은 최 단 로 를 저장 합 니 다!