도 론 입문 의 최 단 로 dijkstra 알고리즘
질문:
출발점 에서 종점 까지 의 가장 짧 은 경 로 를 구 하 는 그림 을 드 리 겠 습 니 다.
방법:
만약 에 d [i] 가 출발점 에서 i 까지 의 가장 짧 은 경 로 를 나타 낸다 면 우리 의 목적 은 모든 d [i] 를 구 한 다음 에 출력 하 는 것 이다. 종점
처음에 우 리 는 먼저 모든 d [i] = inf (하나의 큰 숫자) 를 설정 한 후에 시작 했다.
우선, 우 리 는 우리 의 용감 한 첫 걸음 을 내 디 뎠 습 니 다. d [s] = 0, (s 를 기점 으로) s 에서 출발 하여 근처 의 점 에 도착 하면 근처 의 가장 짧 은 경 로 는 모두 업 데 이 트 될 수 있 습 니 다. 근처 의 점 을 업데이트 한 후에 우 리 는 s 를 삭제 할 것 입 니 다. 왜냐하면 s 는 다른 점 을 업데이트 할 수 없 기 때 문 입 니 다. 그리고 s 는 다른 점 에 의 해 업 데 이 트 될 수 없 기 때문에 다음 에 방문 할 때 바로 건 너 뛰 면 됩 니 다.
현재 s 시 부근의 가장 짧 은 거 리 는 모두 업데이트 되 었 습 니 다. 지금 우 리 는 가장 짧 은 경 로 를 확정 한 점 을 다시 찾 아야 합 니 다.
도대체 어느 점 을 찾 는 거 야???
YY, 잠깐 만, d [i] 제일 작은 i 를 찾 으 면 안 돼 요?
그래!왜?
생각해 보면 알 겠 지.i 점 의 d [i] 가 가장 작 습 니 다. 그의 최 단 로 는 계속 업 데 이 트 될 수 있 습 니까?다른 d [i] 는 그 보다 나이 가 많 기 때문에 다른 점 이 아무리 i 점 으로 돌아 가도 d [i] 를 업데이트 할 수 없습니다.
그래서 저희 알고리즘 이 나 왔 습 니 다.
d [i] 의 가장 작은 i 를 찾 을 때마다 이 i 는 삭제 되 지 않 았 습 니 다. 이 i 로 주변 에 있 는 가장 짧 은 경 로 를 업데이트 하고 이 어 i 를 삭제 합 니 다.
모든 점 이 삭 제 될 때 까지 위 작업 을 반복 합 니 다.그럼 우리 최 단 로 를 빌 자.
다음은 oj 에서 어떤 문제 의 코드 입 니 다.
hdu 2544
#include
#include
const int N = 110;
const int inf = 99999999;
int cost[N][N];
int d[N];
bool deleted[N];
int n , m;
// 1
// cost， d
void Prepare(int s)
{
for(int i = 1; i <= n; i++)
{
cost[i][i] = 0;
for(int j = i + 1; j <= n; j++)
{
cost[i][j] = cost[j][i] = inf;
}
}
for(int i = 1; i <= n; i++) d[i] = inf;
d[s] = 0;
for(int i = 1; i <= n; i++) deleted[i] = false;
}
int Shortest_Path()
{
while(true)
{
int decided = -1;
for(int i = 1; i <= n; i++) if(!deleted[i])
{
if(decided == -1 || d[i] < d[decided]) decided = i;
}
if(decided == -1) break;
//
//printf("decided=%d
",decided);
for(int i = 1; i <= n; i++)
{
if(d[decided] + cost[decided][i] < d[i])
{
d[i] = d[decided] + cost[decided][i];
}
}
deleted[decided] = true;
}
return d[n];
}
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&m),(n||m))
{
Prepare(1);
for(int i = 0; i < m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c < cost[a][b])
{
cost[a][b] = c;
cost[b][a] = c;
}
}
printf("%d
",Shortest_Path());
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
수열 블록 입문 1 ~ 9 문제 풀이그렇지 않 으 면 전체 블록 에 대해 t a g tag 를 직접 수정 하고 다른 분산 요소 에 대해 a [i] a [i] a [i] a [i] a [i] 를 직접 폭력 적 으로 수정 합 니 다. 분산 요소 에 대해 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
