Bellman - ford (BF) 와 Floyd 알고리즘
Floyd 알고리즘 은 비교적 폭력 적 입 니 다. 알고리즘 사상 은 삼중 순환 이 고 모든 정점 을 직접 매 거 합 니 다. 다시 두 번 for 순환 으로 모든 점 을 매 거 합 니 다. 첫 번 째 점 을 중심 으로 하 는 두 점 이 경로 가 더 짧 은 지 검증 하고 구체 적 으로 실현 되 지 않 습 니 다.
Dijkstra 알고리즘 은 마이너스 그림 이 없 는 가장 짧 은 경로 문 제 를 잘 해결 할 수 있 지만 마이너스 값 이 나타 나 면 효력 을 잃 습 니 다.이때 BF 알고리즘 이 필요 합 니 다. BF 와 dj 알고리즘 은 모두 단일 소스 의 가장 짧 은 경로 문 제 를 해결 할 수 있 습 니 다. 그러나 알고리즘 사상 은 완전히 다 릅 니 다. dj 는 출발점 경로 가 가장 짧 은 점 을 선택 한 다음 에 이 점 을 중심 으로 관련 된 경로 가 길 고 가장 바깥쪽 의 n 차 순환 은 n 개의 점 이 모두 방문 할 수 있 습 니 다 (위의 블 로그 참조).
그러나 BF 알고리즘 은 완전히 다 릅 니 다. 가장 바깥쪽 의 n - 1 차 순환 은 n - 1 개의 경 로 를 성공 적 으로 구축 하 는 것 을 보장 하기 위해 서 입 니 다. V - 1 개의 노드 는 V - 1 개의 경로 가 적당 합 니 다. 만약 에 나무 로 전환 하면 깊이 가 V 가 가장 많 습 니 다. 그러나 함수 가 시작 되 기 전에 뿌리 노드 가 방문 되 었 기 때문에 V - 1 번 만 방문 해 야 합 니 다. 사실은 n - 1 번 이 필요 하지 않 고 적당 한 가지치기 가 가능 합 니 다. 예 를 들 어 n 차 순환 에서 if (d [u] + length 등 입 니 다.[u->v]
bool Bellman(int s){
for(int i=0;iv){
if(d[u]+length[u->v]v];
}
}
}
for(each dege u->v){
if(d[u]+length[u->v] 다음으로 전송:https://www.cnblogs.com/tao7/p/10244896.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
