희소 도 에 있 는 Johnson 알고리즘 에 대한 상세 한 설명
1.계산 도 G 에 새 노드 를 추가 한 그림 G',추가 한 새 노드 0 에서 모든 원 노드 사이 의 거 리 는 0 이 며,동시에 새로운 변 집합 E'를 형성한다.
2.벨 맨-ford 알고리즘 을 사용 하여 G'를 처리 하고 0 점 에서 각 노드 까지 의 최소 거리 d 를 형성한다.
3.Bellman-ford 알고리즘 에서 마이너스 회로 가 검출 되면 FALSE 를 알 리 고 종료 합 니 다.그렇지 않 으 면 계속 합 니 다.
4.모든 G'의 정점 v 에 대해 0 점 에서 v 까지 의 최소 거리 에 따라 h(v)를 이 값 으로 설정 합 니 다.
5.모든 사 이 드 w(u,v)에 대한 가중치 업데이트 w(u,v)+h(u)-h(v)
6.그림 G 의 모든 노드 에 대해 Dijkstra 알고리즘 을 실행 하고 다른 정점 과 가장 짧 은 거리 d'[u][v]
(여기 서 G 와 w 집합 이 분리 되 어 저장 된다 고 가정 합 니 다.G'를 직접 사용 해도 된다.0 결점 은 다른 결점 에 도달 할 수 없 기 때문에 계산 시간 을 낭비 한 것 이 분명 하 다.가중치 정보 가 G'에 존재 하면 G'를 조작 할 수 있 습 니 다.0 노드 의 처 리 를 건 너 뛰 었 을 뿐 입 니 다)
7.원 그림 G 중 최 단 거리 d[u][v]=d'[u][v]+h(v)-h(u)
코드 중의 일부 부분 은 최적화 되 지 않 았 다.예 를 들 어 보조 구조 vassist 는 사실 Bellman-ford 알고리즘 과 Dijkstra 알고리즘 두 함수 에서 용법 이 약간 다 르 고 구성원 변 수 는 전자 에서 2 개 만 사용 했다.이완 알고리즘 인 relax 도 비슷 한 경우 가 있다.전 자 는 간단 한 복용 이 고 후 자 는 직접 이름 으로 구분한다.
코드 는 세 부분 을 포함 합 니 다.Bellman-ford 알고리즘,Dijkstra 알고리즘,두 가지 로 이 루어 진 우선 순위 배열(Dijkstra 알고리즘 사용)입 니 다.다음은 알고리즘 의 C 언어 버 전 입 니 다.테스트 실례 는 그림 25-1
#include <stdio.h>
#include <stdlib.h>
#define U 65535
#define PARENT(i) ((i-1)/2)
#define LEFT(i) (2*(i)+1)
#define RIGHT(i) (2*(i)+2)
#define N 5
struct vertex {
int key;
struct vtable *adj;
};
struct vtable {
int key;// key vertex
//struct vertext *v;
int w;
struct vtable *next;
};
struct vassist {
int d;
int p;
int key;
};
int insert(struct vertex *,int,int,int,int);
int walk(struct vertex *,int,int);
struct vassist *initialize_ss(int,int);
int relaxd(int *,int ,int ,int);
int relaxb(struct vassist *,int ,int ,int);
int build_min_heap(struct vassist *,int);
int min_heapify(struct vassist *, int ,int);
int heap_extract_min(struct vassist *,int);
int inheap(struct vassist *,int ,int );
int heap_decrease(struct vassist *,int ,int);
int dijkstra(struct vertex *,int,int,int **);
int bellman_ford(struct vertex *,int*, int,int);
int insert(struct vertex *p,int len,int i,int j,int w) {
struct vtable *q,*prev;
q = p[i].adj;
printf("key:%d
",p[i].key);
prev = NULL;
while(q!=NULL) {
if (q->key == j) {
printf("error: v %d to %d already exist.
",i,j);
return 0;
}
else {
prev = q;
q=q->next;
}
}
q = (struct vtable*)malloc(sizeof(struct vtable));
q->key = j;
q->w = w;
q->next = NULL;
if(prev!=NULL)
prev->next = q;
else
p[i].adj = q;
return 1;
}
int walk(struct vertex *p,int len,int i) {
struct vtable *q = p[i].adj;
while(q!=NULL) {
printf(" %d,w is %d
",q->key,q->w);
q=q->next;
}
printf("
");
}
struct vassist *initialize_ss(int size,int s) {
int i;
struct vassist *va;
va = (struct vassist *)malloc(size*sizeof(struct vassist));
for(i=0;i<size;i++) {
va[i].key = i;// i!=key
va[i].d = U;
va[i].p = -1;
}
va[s].d = 0;
return va;
}
//relax for dijkstra
int relaxd(int *p,int u,int v,int w) {//w=w(u,v)
if(p[v]>p[u]+w) {
p[v] = p[u]+w;
// ,p
//
// , p
}
return 1;
}
//relax for beltman_ford
int relaxb(struct vassist *va,int u,int v,int w) {//w=w(u,v)
if(va[v].d>va[u].d+w) {
va[v].d = va[u].d+w;
va[v].p = u;
}
return 1;
}
int bellman_ford(struct vertex *graph,int *h,int size,int s) {//
int i,j;
struct vtable *p;
struct vassist *va;
va = initialize_ss(size,s);
for(i=1;i<size;i++)
for(j=0;j<size-1;j++) {
p = graph[j].adj;
while(p!=NULL) {
relaxb(va,j,p->key,p->w);
p=p->next;
}
}
printf("from %d,
",s);
for(j=0;j<size;j++)
printf("to %d: %d
",j,va[j].d);
for(j=0;j<size;j++) {// 0
p = graph[j].adj;
while(p!=NULL) {
if(va[p->key].d>va[j].d+p->w)
return 0;
p = p->next;
}
}
for(j=1;j<=size;j++)
h[j] = va[j].d;
free(va);
h[0] = 0;
return 1;
}
int build_min_heap(struct vassist *va,int size) {//
int i;
for (i =size/2-1; i>=0; i--)
min_heapify(va,i,size);
return 1;
}
int min_heapify(struct vassist *va, int i,int heap_size) {
int l,r,min;
struct vassist temp;
int tmin = U;
l = LEFT(i);
r = RIGHT(i);
if ((l < heap_size) &&(va[l].d<va[i].d)) {
min = l;
tmin = va[l].d;
}
else {
min = i;
tmin = va[i].d;
}
if ((r < heap_size) &&(va[r].d<va[min].d)) {
min = r;
tmin = va[r].d;
}
if (!(min == i)) {
temp.d = va[min].d;
temp.p = va[min].p;
temp.key = va[min].key;
va[min].d = va[i].d;
va[min].p = va[i].p;
va[min].key = va[i].key;
va[i].d = temp.d;
va[i].p = temp.p;
va[i].key = temp.key;
min_heapify(va,min,heap_size);
}
return 1;
}
int heap_extract_min(struct vassist *va,int heap_size) {
int min;
if ( heap_size<1 )
return -1;
min = va[0].key;
va[0].p = va[heap_size -1].p;
va[0].d = va[heap_size -1].d;
va[0].key = va[heap_size -1].key;
heap_size = heap_size -1;
min_heapify(va,0,heap_size);
return min;
}
int inheap(struct vassist *va,int heap_size,int j) {
int i;
for(i=0;i<heap_size;i++)
if(va[i].key == j)
return i;
return -1;
}
int heap_decrease(struct vassist *va,int i,int key_new) {
struct vassist temp;
if(key_new>va[i].d)
return 0;
va[i].d = key_new;
while((i>0)&&(va[PARENT(i)].d > va[i].d)) {
temp.d = va[i].d;
temp.p = va[i].p;
temp.key = va[i].key;
va[i].d = va[PARENT(i)].d;
va[i].p = va[PARENT(i)].p;
va[i].key = va[PARENT(i)].key;
va[PARENT(i)].d = temp.d;
va[PARENT(i)].p = temp.p;
va[PARENT(i)].key = temp.key;
i = PARENT(i);
}
return 1;
}
int dijkstra(struct vertex *graph,int len,int s,int **delta) {
int i,j,heap_size;
struct vtable *q;
struct vassist *va;
int *p;
p = (int *)malloc(len * sizeof(int));
for(i=0;i<len;i++)
p[i] = U;
p[s] = 0;
heap_size = len;
va = initialize_ss(len,s);
build_min_heap(va,heap_size);//va ,
while(heap_size>0) {
i = heap_extract_min(va,heap_size);
printf("node:%d
",i);
heap_size--;
for(j=0;j<heap_size;j++)
printf("key:%d,d:%d, in array:%d
",va[j].key,va[j].d,p[va[j].key]);
q = graph[i].adj;
while(q!=NULL) {
j=inheap(va,heap_size,q->key);
if(j>=0)
if(va[j].d>p[i]+q->w)
heap_decrease(va,j,p[i]+q->w);
relaxd(p,i,q->key,q->w);// heap_decreas relax,
printf("relax %d to %d ,w is %d
",i,q->key,q->w);
q = q->next;
}
for(j=0;j<heap_size;j++)
printf("key:%d,d:%d, in array:%d
",va[j].key,va[j].d,p[va[j].key]);
}
for(i=0;i<len;i++)
printf("from %d to %d, distance is %d
",s,i,p[i]);
free(va);
for(i=0;i<len;i++) {
delta[s][i] = p[i];
}
free(p);
}
int **johnson(struct vertex *g, int n) {
int i,j;
int *h,**delta,**d;
struct vertex *gn;
struct vtable *p;
gn = (struct vertex *)malloc(n*sizeof(struct vertex));
h = (int *)malloc(n*sizeof(int));
delta = (int**)malloc(n*sizeof(int *));
d = (int**)malloc(n*sizeof(int *));
for(i=0;i<n;i++) {
delta[i]=(int*)malloc(n*sizeof(int));
d[i]=(int*)malloc(n*sizeof(int));
}
for(i=0;i<n;i++)
gn[i] = g[i];
for(i=1;i<n;i++)
insert(gn,n,0,i,0);
if(!bellman_ford(gn,h,n,0)) {
printf("the input graph contains a negative-weight cycle.
");
return NULL;
}
for(i=0;i<n;i++) {
p = gn[i].adj;
while(p!=NULL) {
p->w = p->w+h[i]-h[p->key];
p=p->next;
}
}
for(i=0;i<n;i++)
walk(gn,n,i);
printf("before dijkstra
");
for(i=1;i<n;i++) {
dijkstra(gn,n,i,delta);
for(j=1;j<n;j++)
d[i][j] = delta[i][j] + h[j] - h[i];
}
for(i=1;i<n;i++) {
for(j=1;j<n;j++)
printf("%d\t",d[i][j]);
printf("
");
}
return d;
}
int main(){
int i,j;
int **d;
struct vertex vt[N+1];// 0
for(i=0;i<N+1;i++) {
vt[i].adj = NULL;
vt[i].key = i;
}
insert(vt,N+1,1,2,3);
insert(vt,N+1,1,3,8);
insert(vt,N+1,1,5,-4);
insert(vt,N+1,2,4,1);
insert(vt,N+1,2,5,7);
insert(vt,N+1,3,2,4);
insert(vt,N+1,4,3,-5);
insert(vt,N+1,4,1,2);
insert(vt,N+1,5,4,6);
d = johnson(vt,N+1);
return 1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【JavaScript】 볼록함 그라함 스캔을 구현, 애니메이션화한다! ? 【canvas】볼록포를 시각화해 본다. — s-yoshiki | 스크립트 카스 (@s_yoshiki_dev) JavaScript에서 그레이엄 스캔에 의해 정렬되어 가는 애니메이션을 구현했다. 아래쪽에서 데모로 소개. 참고 Java...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
