文档章节

Johnson算法

pior
 pior
发布于 2017/01/13 14:53
字数 2602
阅读 70
收藏 1

Johnson算法可以在O(V*V lgV + VE)的时间内找到所有节点对之间的最短路径,对于稀疏图来说,算法的渐进表现要由于重复平方法和FloydWarshall算法,如果图没有权值为负值的环路,则返回所有结点对的最短路径权重的矩阵,否则,报告图有权值为负的环

算法中运用Diskra、BellmanFord算法,使用的技术是重新赋予权重,

如果图G = (V, E)中权值全为非负值,则通过对所有结点运行一次dijkstra算法找出所有结点对的最短路径,

如果有非负值,但没有权重为负值的环路,那么只要计算出一组新的非负权重值,然后再用相同的方法即可。

 

对于将负值权重转换为非负值使用的方法是,在原图上新加一个结点s,并将w(s, v) == 0, 然后对s运行BellmanFord函数计算出s到其他点的最短路径,

运用一个h[vexnum]数组存放这个值,h[i] = σ(s, v),即s到v的最短路径值。

这个值相当于将每个结点赋予一个一个值,这些值用于重新计算边的权重ww(u, v) = w(u, v) + h(u) - h(v),重新计算出来的权重即为非负值。

 

以下是代码的运行过程图,书410页:



以下为代码:

    import java.util.*;  
    public class Johnson{  
        static final int MAX = 20;  //最大点数  
        static int[][] g;  
        static int[] h = new int[MAX];  
    //  static LinkedList<Elem> S = new LinkedList<Elem>();    
        static PriorityQueue<Elem> Q = new PriorityQueue<Elem>(); //Q = V-S    
        static ArrayList<Elem> nodes = new ArrayList<Elem>();  
        static int[][] D;  
          
        static int ver;  //节点数  
            static int edge; //边数  
            static final int BELLMAN_FORD = 1;  
            static final int DIJKSTRA = 2;  
            /************全局数据结构****************/  
        static class Elem implements Comparable<Elem>    
        {    
            public int s; //节点编号   
            public int d;  //与源节点距离  
            public Elem(int s,int d){    
                    this.s = s;    
                    this.d = d;    
            }  
            public int compareTo(Elem e){return d - e.d;}    
        }  
        /***********以下是Johnson算法实现*******************/  
        static void johnson(){  
              
            int s = ver; //新添加一个节点  
            int[][] g_new = new int[ver+1][ver+1];  
            for(int u = 0;u < g_new.length;u++){  
                for(int v = 0;v < g_new.length;v++){  
                    if(v == g.length){g_new[u][v] = Integer.MAX_VALUE;continue;}  
                    if(u == g.length){g_new[u][v] = 0; continue;}  
                    g_new[u][v] = g[u][v];  
                }  
            }  
              
            if(bellman_ford(g_new,s) == false) {System.out.println("circle exist");return;}  
              
            for(Elem e:nodes) h[e.s] = e.d;  
            System.out.println("h[v]: from 0 to n");  
            for(int i = 0;i<g.length;i++) System.out.print(h[i]+" "+'\t');  
            System.out.println();  
            for(int u = 0;u < ver;u++){  
                for(int v = 0;v < ver;v++){  
                    if(g[u][v] == Integer.MAX_VALUE) continue;  
                    g[u][v] = g[u][v] + h[u]-h[v];  
                }  
            }  
            System.out.println("G' :");  
            initD(g);  
            print(g);  
            for(int u = 0;u < ver;u++){  
                dijkstra(g,u);  
                for(int v = 0;v < ver;v++){  
                    if(nodes.get(v).d == Integer.MAX_VALUE) continue;  
                    D[u][v] = nodes.get(v).d + h[v] - h[u];  
                }  
            }  
              
            System.out.println("D[i][j]: shortest path from i to j");  
            print(D);  
              
        }  
          
        public static void main(String[] args){  
            input();  
            johnson();  
        }  
          
        /***初始化函数:可用于Bellman-Ford与Dijkstra的初始化*******/  
        static void init(int[][] g,int source,int mode){   
            nodes.clear();   
            for(int i=0; i < g.length;i++){    
                //初始S为空,Q为全部节点    
                Elem e = new Elem(i,Integer.MAX_VALUE);    
                nodes.add(e);    
                if(i == source && mode == DIJKSTRA) Q.add(e);  
            }  
            nodes.get(source).d = 0;  
        }  
        static void initD(int[][] g){      
            for(int i = 0;i < g.length;i++)      
                for(int j = 0;j < g.length;j++){      
                    D[i][j] = g[i][j];      
                }      
            }      
        /*********以下是Bellman-Ford实现***********/  
        static boolean bellman_ford(int[][] g,int source){      
            init(g,source,BELLMAN_FORD);     
            int s=0,e=0,w=0;        
            for(int i=0;i < g.length-1;i++){      
                //对所有的边进行松弛操作  
                for(int u = 0;u < g.length;u++){  
                    for(int v = 0;v < g.length;v++){  
                        if(g[u][v] == Integer.MAX_VALUE||nodes.get(u).d == Integer.MAX_VALUE) continue;  
                        nodes.get(v).d = Math.min(nodes.get(v).d, nodes.get(u).d + g[u][v]);  
                    }  
                }  
            }      
            //遍历每条边      
            for(int u = 0;u < g.length;u++){  
                for(int v = 0;v < g.length;v++){   
                    if(g[u][v] == Integer.MAX_VALUE||nodes.get(u).d == Integer.MAX_VALUE) continue;  
                    if(nodes.get(v).d > nodes.get(u).d + g[u][v]) return false;  
                }  
            }      
            return true;      
        }  
            /************以下是Dijkstra实现*************/  
          
        static void dijkstra(int[][] g,int source){    
            init(g,source,DIJKSTRA);  
            while(Q.size() > 0){    
                Elem u = Q.poll();    
    //          S.add(u);    
                for(int v = 0;v < g.length;v++){    
                if(g[u.s][v] != Integer.MAX_VALUE && nodes.get(v).d > u.d + g[u.s][v]){    
                    Elem nv = nodes.get(v);    
                    //下面删除后添加是为了使PriorityQueue能够重新调整    
                    Q.remove(nv);    
                    nv.d = u.d + g[u.s][v];    
                    Q.offer(nv);    
                }    
                }    
            }  
        }  
        /**************用于获取输入数据,初始化图G的***************/  
        static void input(){    
            Scanner cin = new Scanner(System.in);    
            System.out.println("请输入 点数 边数");    
            ver = cin.nextInt();    
            edge = cin.nextInt();    
            g  = new int[ver][ver];  
            D = new int[ver+1][ver+1];  
            int s,e,w;  
            for(int i = 0;i < ver;i++){  
                for(int j = 0;j < ver;j++) {g[i][j] = Integer.MAX_VALUE;}  
            }  
            System.out.println("起点 终点 权值");    
            for(int i=0;i<edge;i++){    
                s = cin.nextInt();    
                e = cin.nextInt();    
                w = cin.nextInt();    
                g[s][e] = w;    
            }    
        }  
        /************打印前驱矩阵**************/  
        static void print(int[][] g){  
            for(int u = 0;u < ver;u++){  
                for(int v = 0;v < ver;v++){  
                    if(g[u][v] == Integer.MAX_VALUE){System.out.print("inf\t"); continue;}  
                    System.out.print(g[u][v]+""+'\t');  
                }  
                System.out.println();  
            }  
        }  
    }  

C++版:

/************************************************************ 
Johnson.h: Johnson算法,存储为邻接表, 
Date: 2014/1/5 
Author: searchop 
************************************************************/  
  
#ifndef ALGRAPH_H  
#define ALGRAPH_H  
  
#include <vector>  
#include <queue>  
#include <stack>  
#include <iostream>  
#include <algorithm>  
#include <functional>  
using namespace std;  
  
//邻接表的结构  
struct ArcNode          //表结点  
{  
    int source;        //图中该弧的源节点  
    int adjvex;        //该弧所指向的顶点的位置  
    ArcNode *nextarc;  //指向下一条弧的指针  
    int weight;         //每条边的权重  
};  
  
template <typename VertexType>  
struct VertexNode           //头结点  
{  
    VertexType data;    //顶点信息  
    ArcNode *firstarc;  //指向第一条依附于该顶点的弧的指针  
    int key;            //Prim:保存连接该顶点和树中结点的所有边中最小边的权重;   
                        //BellmanFord:记录从源结点到该结点的最短路径权重的上界  
    VertexNode *p;      //指向在树中的父节点  
    int indegree;       //记录每个顶点的入度  
};  
  
const int SIZE = 6;  
  
//图的操作  
template <typename VertexType>  
class ALGraph  
{  
public:  
    typedef VertexNode<VertexType> VNode;  
    ALGraph(int verNum) : vexnum(verNum), arcnum(0)  
    {  
        for (int i = 0; i < MAX_VERTEX_NUM; i++)  
        {  
            vertices[i].firstarc = NULL;  
            vertices[i].key = INT_MAX/2;  
            vertices[i].p = NULL;  
            vertices[i].indegree = 0;  
        }  
    }  
  
    //构造算法导论410页图(带权有向图)  
    void createWDG()  
    {  
        cout << "构造算法导论410页图(带权有向图)..." << endl;  
        int i;  
        for (i = 1; i < vexnum; i++)  
            vertices[i].data = 'a' + i - 1;       
  
        insertArc(1, 2, 3);  
        insertArc(1, 3, 8);  
        insertArc(1, 5, -4);  
        insertArc(2, 4, 1);  
        insertArc(2, 5, 7);  
        insertArc(3, 2, 4);  
        insertArc(4, 3, -5);  
        insertArc(4, 1, 2);  
        insertArc(5, 4, 6);  
    }  
  
    void createG()  
    {  
        cout << "构造图G'...." << endl;  
        vertices[0].data = 's';  
        insertArc(0, 1, 0);  
        insertArc(0, 2, 0);  
        insertArc(0, 3, 0);  
        insertArc(0, 4, 0);  
        insertArc(0, 5, 0);  
    }  
  
    //Johnson算法,先使用BellmanFord算法,使所有的边的权重变为非负值,  
    //然后运用dijkstra算法求出结点对的最短路径  
    int **Johnson()  
    {  
        createG();          //构造G’  
        displayGraph();  
  
        if (!BellmanFord(1))  
           cout << "the input graph contains a negative-weight cycle" << endl;  
        else  
        {  
            int h[SIZE];  
            int i, j, k;  
  
            //将数组h[]的值设为运行BellmanFord后取得的值,h[i]为结点s到其他点的最短路径  
            for (i = 0; i < vexnum; i++)  
                h[i] = vertices[i].key;  
            //遍历所有的边,将边的权值重新赋值,即将所有的边的权值改为负值  
            for (i = 0; i < vexnum; i++)  
            {  
                ArcNode *arc = vertices[i].firstarc;  
                for (; arc != NULL; arc = arc->nextarc)  
                    arc->weight = arc->weight + h[arc->source] - h[arc->adjvex];  
            }     
            以下为代码:  
                        cout << "改变权重后的图为:" << endl;                                                                                                                     displayGraph();  
            int **d = new int *[SIZE];  
            for (j = 0; j < SIZE; j++)  
                d[j] = new int[SIZE];  
            //对每个结点运行dijkstra算法,求出每个点到其他点的最短路径,保存在key中  
            for (k = 1; k < SIZE; k++)  
            {  
                Dijkstra(k+1);  
                for (i = 1; i < SIZE; i++)  
                    d[k][i] = vertices[i].key + h[i] - h[k];  
            }  
            cout << "最后计算出的结点对的最短距离:" << endl;  
            displayTwoDimArray(d);  
            return d;  
        }  
    }  
  
    //输出一个二维数组  
    void displayTwoDimArray(int **p)  
    {  
        for (int i = 0; i < SIZE; i++)  
        {  
            for (int j = 0; j < SIZE; j++)  
                cout << p[i][j] << " ";  
            cout << endl;  
        }  
        cout << "~~~~~~~~~~~~~~~" << endl;  
    }  
  
    //打印邻接链表  
    virtual void displayGraph()  
    {  
        for (int i = 0; i < vexnum; i++)  
        {  
            cout << "第" << i+1 << "个顶点是:" << vertices[i].data  
                << " 顶点的入度为:" << vertices[i].indegree << " 邻接表为: ";  
            ArcNode *arcNode = vertices[i].firstarc;  
            while (arcNode != NULL)  
            {  
                cout << " -> " << vertices[arcNode->adjvex].data  
                    << "(" << arcNode->weight << ")";  
                arcNode = arcNode->nextarc;  
            }  
            cout << endl;  
        }  
        cout << "*******************************************************" << endl;  
    }  
  
    //PVnode排序准则  
    class PVNodeCompare  
    {  
    public:  
        bool operator() (VNode *pvnode1, VNode *pvnode2)  
        {  
            return pvnode1->key > pvnode2->key;  
        }  
    };  
  
    //对每个结点的最短路径估计和前驱结点进行初始化,最短路径初始化为INT_MAX, p初始化为NULL  
    //并将源节点的key初始化为0  
    void InitalizeSingleSource(int index)  
    {  
        for (int i = 0; i < MAX_VERTEX_NUM; i++)  
        {  
            vertices[i].key = INT_MAX>>2;  
            vertices[i].p = NULL;  
        }  
        vertices[index].key = 0;  
    }  
  
    //对边(u, v)进行松弛,将目前s到v的最短路径v.key与s到u的最短路径加上w(u, v)的值进行比较  
    //如果比后面的值还大,则进行更新,将v.key缩短,并且将p置为u  
    void relax(ArcNode *arc)  
    {  
        //竟然溢出了!!  
        if (vertices[arc->adjvex].key > vertices[arc->source].key + arc->weight)  
        {  
            vertices[arc->adjvex].key = vertices[arc->source].key + arc->weight;  
            vertices[arc->adjvex].p = &vertices[arc->source];  
        }  
    }  
  
    //BellmanFord, index为实际第几个点  
    bool BellmanFord(int index)  
    {  
        InitalizeSingleSource(index-1);  
        for (int i = 1; i < vexnum; i++)     //循环共进行vexnum-1次  
        {  
            //遍历所有的边,并对每个边进行一次松弛  
            for (int j = 0; j < vexnum; j++)  
            {  
                for (ArcNode *arc = vertices[j].firstarc; arc != NULL; arc = arc->nextarc)  
                    relax(arc);  
            }  
        }  
        //再次遍历所有的边,检查图中是否存在权重为负值的环路,如果存在,则返回false  
        for (int j = 0; j < vexnum; j++)  
        {  
            for (ArcNode *arc = vertices[0].firstarc; arc != NULL; arc = arc->nextarc)  
            {  
                if (vertices[arc->adjvex].key > vertices[arc->source].key + arc->weight)  
                    return false;  
            }  
        }  
        cout << "BellmanFord求出的单源最短路径:" << endl;  
        for (int i = 1; i < vexnum; i++)  
        {  
            printPath(index-1, i);  
        }  
        cout << "**************************************************" << endl;  
        return true;  
    }  
  
    void Dijkstra(int index)  
    {  
        InitalizeSingleSource(index-1);  
        vector<VNode> snode;       //保存已经找到最短路径的结点  
        vector<VNode *> que;       //保存结点的指针的数组,用这个数组执行堆的算法  
  
        //将结点指针进队列,形成以key为关键值的最小堆  
        for (int i = 0; i < vexnum; i++)  
            que.push_back(&(vertices[i]));  
        //使que按照pvnodecompare准则构成一个最小堆  
        make_heap(que.begin(), que.end(), PVNodeCompare());     
  
        while (que.empty() == false)  
        {  
            //将队列中拥有最小key的结点出队  
            VNode *node = que.front();  
            pop_heap(que.begin(), que.end(), PVNodeCompare());   //从堆中删除最小的结点,只是放到了vector的最后  
            que.pop_back();      //将vector中的这个结点彻底删除,因为后面还要再排序一次,以免影响后面的堆排序,pop算法。  
            snode.push_back(*node);  
            for (ArcNode *arc = node->firstarc; arc != NULL; arc = arc->nextarc)  
                relax(arc);  
            make_heap(que.begin(), que.end(), PVNodeCompare());  
        }  
        cout << "Dijkstra求出的单源最短路径:" << endl;  
        for (int i = 1; i < vexnum; i++)  
        {  
            if (i != index-1)  
               printPath(index-1, i);  
        }  
        cout << "**************************************************" << endl;  
    }  
  
protected:  
    //插入一个表结点  
    void insertArc(int vHead, int vTail, int weight)  
    {  
        //构造一个表结点  
        ArcNode *newArcNode = new ArcNode;  
        newArcNode->source = vHead;  
        newArcNode->adjvex = vTail;  
        newArcNode->nextarc = NULL;  
        newArcNode->weight = weight;  
  
        //arcNode 是vertics[vHead]的邻接表  
        ArcNode *arcNode = vertices[vHead].firstarc;  
        if (arcNode == NULL)  
            vertices[vHead].firstarc = newArcNode;  
        else  
        {  
            while (arcNode->nextarc != NULL)  
            {  
                arcNode = arcNode->nextarc;        
            }  
            arcNode->nextarc = newArcNode;  
        }  
        arcnum++;  
        vertices[vTail].indegree++;         //对弧的尾结点的入度加1  
    }  
  
    //打印源节点到i的最短路径  
    void printPath(int i, int j)  
    {  
        cout << "从源节点 " << vertices[i].data << " 到目的结点 "  
            << vertices[j].data << " 的最短路径是:" /*<< endl*/;  
        __printPath(&vertices[i], &vertices[j]);  
        cout << " 权重为:" << vertices[j].key << endl;  
    }  
  
    void __printPath(VNode* source, VNode* dest)  
    {  
        if (source == dest)  
            cout << source->data << "->";  
        else if (dest->p == NULL)  
            cout << " no path!" << endl;  
        else  
        {  
            __printPath(source, dest->p);  
            cout << dest->data << "->";  
        }  
    }  
  
private:  
    //const数据成员必须在构造函数里初始化  
    static const int MAX_VERTEX_NUM = 20;  //最大顶点个数  
  
    VNode vertices[MAX_VERTEX_NUM];      //存放结点的数组  
    int vexnum;             //图的当前顶点数  
    int arcnum;             //图的弧数  
};  

 

本文转载自:

pior
粉丝 27
博文 151
码字总数 22496
作品 0
济南
高级程序员
私信 提问

暂无文章

32位与64位Linux系统下各类型长度对比

64 位的优点:64 位的应用程序可以直接访问 4EB 的内存和文件大小最大达到4 EB(2 的 63 次幂);可以访问大型数据库。本文介绍的是64位下C语言开发程序注意事项。 1. 32 位和 64 位C数据类型...

mskk
28分钟前
6
0
Vue 实现点击空白处隐藏某节点(三种方式:指令、普通、遮罩)

在项目中往往会有这样的需求: 弹出框(或Popover)在 show 后,点击空白处可以将其 hide。 针对此需求,整理了三种实现方式,大家按实际情况选择。 当然,我们做项目肯定会用到 UI 框架,常...

张兴华ZHero
34分钟前
7
0
SpringBoot激活profiles你知道几种方式?

多环境是最常见的配置隔离方式之一,可以根据不同的运行环境提供不同的配置信息来应对不同的业务场景,在SpringBoot内支持了多种配置隔离的方式,可以激活单个或者多个配置文件。 激活Profi...

恒宇少年
36分钟前
8
0
PDF修改文字的方法有哪些?怎么修改PDF文件中的文字

PDF修改文字一直以来都是一个难以解决的问题,很多的办公族在办公的时候会有修改PDF文件中的文字的需要,可是PDF文件一般是不能进行编辑和修改的,难道就没有什么办法解决这个问题了嘛?不要...

趣味办公社
39分钟前
5
0
企业组织中采用服务网格的挑战

作者:Christian Posta 译者:罗广明 原文:https://blog.christianposta.com/challenges-of-adopting-service-mesh-in-enterprise-organizations/ 编者按 本文作者介绍了企业组织采用服务网...

jimmysong
48分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部