基于稀疏图上的Johnson算法的详解_C 语言

算法步骤简述:

1.计算图G加入新结点后的图G',加入的新结点0到所有原结点之间距离为0,同时形成新的边集E';

2.使用Bellman-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\n",p[i].key);
    prev = NULL;
    while(q!=NULL) {
        if (q->key == j) {
            printf("error: v %d to %d already exist.\n",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\n",q->key,q->w);
        q=q->next;
    }
    printf("\n");
}

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,\n",s);
    for(j=0;j<size;j++)
        printf("to %d: %d\n",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\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;
}

时间: 2024-09-11 00:23:00

基于稀疏图上的Johnson算法的详解_C 语言的相关文章

标准CSV格式的介绍和分析以及解析算法实例详解_C 语言

     CSV是一种古老的数据传输格式,它的全称是Comma-Separated Values(逗号分隔值).出生在那个标准缺失的蛮荒年代,CSV的标准一直(到2005年)是NULL--世间存在着N种CSV格式,它们自成体系,相互不兼容.比如我们从名字可以认为CSV至少是一种使用逗号分隔的格式,但是实际上,有的CSV格式却是使用分号(;)去做分隔.假如,不存在一种标准,那么这东西最终会因为碎片化而发展缓慢,甚至没落.本文讨论的CSV格式是基于2005年发布的RFC4180规范.我想,在这个规范

深入N皇后问题的两个最高效算法的详解_C 语言

N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行.同一列.同一斜线上的皇后都会自动攻击).一. 求解N皇后问题是算法中回溯法应用的一个经典案例回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试.在现实中,有很多问题往往需要我们把其所有可能穷举出来,然后从中找出满足某种要求的可能或最优的情况,从而得到整个问题的解.回溯算法就是解决这种问题的"通用算法",有&qu

基于C++中常见编译错误的总结详解_C 语言

在日常编码过程中会遇见各种编译错误,本文对常见的编译错误进行分析总结.(基本的编译错误在这里不列举,后续后持续更新) 1.error c101008a解决方法该错误出现在项目升级过程中会出现,比如说项目从vs2008升级到vs2010.解决办法:在项目上点右键,清理(Clean),重新编译,问题解决 2.error C2252解决方法该错误主要在项目从vs2008升级到vs2010出先.error C2252: an explicit instantiation of a template ca

基于C++全局变量的声明与定义的详解_C 语言

(1)编译单元(模块)在VC或VS上编写完代码,点击编译按钮准备生成exe文件时,编译器做了两步工作:第一步,将每个.cpp(.c)和相应的.h文件编译成obj文件:第二步,将工程中所有的obj文件进行LINK,生成最终.exe文件.那么,错误可能在两个地方产生:一个,编译时的错误,这个主要是语法错误:一个,链接时的错误,主要是重复定义变量等.编译单元指在编译阶段生成的每个obj文件.一个obj文件就是一个编译单元.一个.cpp(.c)和它相应的.h文件共同组成了一个编译单元.一个工程由很多编译

基于C中含有if的宏定义详解_C 语言

含有if的宏定义当宏定义中含有 if 时1) 定义如下宏#define DC(p) if( foo(p) )fun(p)用在下面的环境中if(k>n)DC(k);elseDC(n);宏替换后,如下if(k>n)if( foo(k) )fun(k);elseif( foo(n) )fun( n );可见, 原来的 if 和 else 不再配对.2) 为了避免这类问题, 我们可以将包含if语句的宏定义为一个整体.#define DC(p) {if( foo(p) ) fun(p);}但是, 替换后

基于排列与组合输出多少中情况详解_C 语言

排列 复制代码 代码如下: #include <stdio.h>// 主要是找到当前要排的 和后面要排数的关系int swap(int m,int n){ if(n==1)  return m-n+1; return  m*swap(m-1,n-1); }int main(){ int m=5,n=4; printf("%d",swap(5,4)); } 组合 计算3个A,2个B可以组成多少种排列的问题 思路一: 复制代码 代码如下: #include <stdio.

C语言实现排序算法之归并排序详解_C 语言

排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

贪心算法的C语言实现与运用详解_C 语言

贪心算法 所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解.贪心算法的基本思路如下: 1.建立数学模型来描述问题. 2.把求解的问题分成若干个子问题. 3.对每一子问题求解,得到子问题的局部最优解. 4.把子问题的解局部最优解合成原来解问题的一个解.   实现该算法的过程: 从问题的某一初始解出

基于一致性hash算法 C++语言的实现详解_C 语言

    一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择.     首先来谈一下一致性hash算法中用于存储结点的数据结构.通过了解一致性hash的原理,我们知道结点可以想象为是存储在一个环形的数据结构上(如下图),结点A.B.C.D按hash值在环形分布上是有序的,也就是说结点可以按hash值存储在一个有序的队列里.如下图所示,当一个hash值为-2^20的请求点P查找路由结点时,一致性hash算法会按hash值的顺时针方向