도 론 입문 의 최 단 로 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()); } }

좋은 웹페이지 즐겨찾기