c+Bellman-ford 알고리즘 의 구체 적 인 실현
2742 단어 c + +Bellman-Ford
그 시간 복잡 도 는 O(nm)로 효율 이 비교적 낮다.
코드 구현:
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e4+10;
const int M=510;
int m,n,k,dis[M],backup[M];
//m ，n ， 1 n k
//dis： ，backup：
struct Node
{
int x,y,v;
}edge[N];//
int Bellman_Ford()
{
dis[1]=0;
memset(dis,0x3f,sizeof dis);
for(int i=1;i<=k;i++)
{
memcpy(backup,dis,sizeof dis);
for(int j=1;j<=m;j++)
{
Node t=edge[j];
dis[t.y]=min(dis[t.y],backup[t.x]+t.v);
}
}
if(dis[n]>inf/2) return -1;
return dis[n];
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
edge[i]={a,b,c};
}
int ans=Bellman_Ford();
if(ans==-1) cout<<"impossible";
else cout<<ans;
return 0;
} 1.backup 백업 배열 에 존재 하 는 의미:매번"교체"후 dis 배열 의 현재 상 태 를 저장 합 니 다.
여기 서'교체'의 의 미 를 상세 하 게 설명 한다.이곳 의 교 체 는 바로 원점 에서 시작 하여 도착 한 점 의 출구 를 이완 시 키 는 것 이다.
예 를 들 어 다음 과 같은 그림 이 있 는데 1 번 점 은 원점 이다.
첫 번 째 교체
2,3 번 점 에서 원점 까지 의 최 단 거 리 를 찾 습 니 다.
이차 교체
4,5 번 점 에서 원점 까지 의 최 단 거 리 를 찾 았 다.
세 번 째 교체
모든 변 이 이미 널리 퍼 져 있 기 때문에,느슨 해 지고,교체 가 끝 날 수 있 는 변 이 없다.
아까 의 과정 을 통 해 알 수 있 듯 이 매번 교체 한 후에 dis 배열 을 백업 해 야 한다.만약 에 dis 배열 을 계속 사용 하여 연산 을 하면 프로그램 은 교체 의 통 제 를 잃 게 된다.(코드 에서 Bellman-ford 함수 중의 외 중 순환 으로 교체 되 고 제목 은 k 개의 변 을 거 쳐 야 한다.실제 적 으로 최대 k 번 의 교체 가 있다)
2.코드 의 마지막 판단
왜 if(dis[n]>inf/2)이지 if(dis[n]==inf)가 아 닙 니까?
이 유 는 Bellman-ford 알고리즘 이 마이너스 변 을 포함 한 그림 을 처리 할 수 있 기 때 문 입 니 다.dis[n]는+표시-2 와 같은 수치 가 나타 날 수 있 기 때문에 크기 비교 판단 을 할 때 조건 은 dis[n]가 같은 수량 급 의 수(여 기 는 inf/2)보다 크 면 됩 니 다.
c++Bellman-ford 알고리즘 의 구체 적 인 실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 c+Bellman-ford 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부탁드립니다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1717 소수 화 점수 2 (수학)소수 화 점수 2 레이 는 수학 시간 에 선생님 의 말씀 을 듣 고 모든 소수 가 점수 로 표시 되 는 형식 이 라 고 말 했다. 그 는 녹 기 시 작 했 고 곧 완성 되 었 다. 그러나 그 는 또 하나의 문 제 를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
