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\n",i);
heap_size--;
for(j=0;j<heap_size;j++)
printf("key:%d,d:%d, in array:%d\n",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\n",i,q->key,q->w);
q = q->next;
}
for(j=0;j<heap_size;j++)
printf("key:%d,d:%d, in array:%d\n",va[j].key,va[j].d,p[va[j].key]);
}
for(i=0;i<len;i++)
printf("from %d to %d, distance is %d\n",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.\n");
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\n");
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("\n");
}
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;
} |
