c++ 无向图 迪杰斯特拉算法_迪杰斯特拉算法 c++ 有向图 - CSDN
精华内容
参与话题
  • 最短路径之Dijkstra(迪杰斯特拉)算法无向图

    万次阅读 多人点赞 2020-04-05 14:27:07
    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。 原理 ...

    简介

     

         Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。

    原理

     

          在已知图的邻接矩阵net.vexs[i][j](无向网,含权值的图)的条件下,过遍历已知图的所有路径,用dis[i]数组来记录到i点的最短路径,然后在循环中不断判断更替。首先,将所有点的集合分为俩部分,一边是已经遍历过的,另外一边是没有遍历过的,分别用mark[i]=1、mark[i]=0来表示。

     

    代码通解

     

                 在下面代码中,先将赋予初始值dis[i]=INF(无穷大)、mark[i]=0(未标记),而后单独将源点(x)所联通的路径权值net.arcs[x][i]赋予dis[i](<INF称为初始化),i为联通的点,暂定为到i的最短路径,标记mark[x]=1,即已经遍历;然后,在一个for遍历了所有节点的大循环里面:

                                                              ①寻找遍历到点联通路径(与之相连线的点)中权值最小的一条; 标记遍历点;

                                                              ②修正最短路径;

    而后,便是已经遍历所有点了,dis[i]也在不断的修正中得到真正的最小值,即最短路径。详情看下列代码

     

     

    #define MAXSIZE 20
    #define PLACENUM 12
    #define INF 9999           // 此处定义999为无穷大
    
    struct
    {
        int vexnum,arcnum;  //节点数和边数
        int vexs[MAXSIZE];      // 节点名
        int arcs[MAXSIZE][MAXSIZE];   //俩个节点之间的值
    } net;
    /*补充的结构体net,2019.7.3*/
    
    void Dijkstra(int x,int y)      // x为源点,y为终点
    {
        int i,j,k;
        int min;
        int u;   //下一个放入集合p的点
        int dis[net.vexnum];   //  最短路径
        int mark[net.vexnum];   //   被mark的便是已经遍历,未被mark的便是未遍历
        /*首先进行最短路径初始化*/
        for(i=0; i<net.vexnum; i++)
        {
            mark[i] = 0;
            dis[i] = net.arcs[x][i];
        }
    
    
        mark[x]=1;          // 标记源点
        
        
        for(k=0; k<net.vexnum; k++)          // for 大循环
        {
            min = INF;   //  min初始化最大值,便于后来数据替换(每一个点的出度入度判断)
            
            /*寻找遍历到点联通路径(与之相连线的点)中权值最小的一条; 标记遍历点;*/
            for(i=0; i<net.vexnum; i++)
            {
                if(mark[i]==0&&min>dis[i])      //判断未遍历点 且 被赋值的最短路径(dis[i]<INF),未被赋值的点     //                                                     应当min==dis[i]=INF
                {
                   min = dis[i];             //在已知赋值最短路径中,寻找权值最小的点并将他作为下一个遍历 
                   u=i;                            //点u点
                }
            }
    
    
            mark[u]=1;      //标记u点,下面u修正将会以最短路径进行辐射
     
            /*修正最短路径*/
            for(i=0;i<net.vexnum;i++)
            {
                if(!mark[i]&&dis[i]>dis[u]+net.arcs[u][i])                 // !mark[i]判断不去走回头路,         //                                                                                dis[i]>dis[u]+net.arcs[u][i]有俩个用途:①若u链接的是x源点没有赋值最短路径的点,那么这里可以赋值②若是赋值过的点,那么可以判断是上一个dis[i](此时是被赋值过的)是不是真正的最短路径,即修正。
    
                {
                    dis[i] = dis[u] + net.arcs[u][i];      //若A->C比A->B->C更长那么A->B->C则是到C的最短路径,下图将解释。
             
                       }
                 }
        }
         printf("最短路径值为:             %d",dis[y]);
    }

     

     

    我们以A,B,C三个点来举例子,三个点的最短路径分别为dis[0]、dis[1]、dis[2]。

     

     

                                                       ①A为源点初始化,dis[B]=3 (到B的最短路径,dis[1]),  dis[C]=6;

                                                       ②dis[B]<dis[C],选取B为u下一个遍历点;与B相联的有A(不走回头路)、E、C;

                                                       ③E未赋值,赋予dis[E];  C被之前赋予过,比较  dis[C] > dis[B] + net.arcs[B][C] (要不然你根本进不了这儿),重新赋值dis[C] = dis[B]+net.arcs[B][C];

                                                       ④大循环遍历所有点,走遍天下。

     

     

     

     

    我觉得下面几张图很不错,图片取自https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

    图一

     

     

     

     

    图二

     

    19.3.24

    关于修正最短路径

    请参考一下文中引入的动图(图一)和表格图(图二),迪杰斯特拉求最短路径是,将需要遍历的点集合一个个进行遍历的。!mark[i]是需要其值为false(尚未遍历到,这是相对于当前遍历点),当然,这就实现了它不会往回走,同时记录它“向前走”的最短距离点u,在其基础上(修正循环),与u点相连的未被标记(遍历到)的点记其中一个为z,判断源点x->z点们的dis(最短)值是否大于x->u->z点们的距离,如果大于,更新z点们的最新(新的路径)最短距离,在已知最短距离的情况下然后进行更新,直到遍历完所有的点集合(所有路径)。从源点往外辐射就能够理解了。

    比如说1,2,3为三角形相互联系。当前是2。已经遍历了1,赋予了1->2、1->3、1->6的dis值,那么在修正部分就会从u(设12、13、16中12距离最小),也就是2往外与没遍历且相邻的3和4判断以下:1->3大于1->2->3?  1->4大于1->2->4?,如果大于,更新dis值,此为修正,这里在已知最短距离1->2的基础上修正了1->3和1->4的dis值。同理到3的时候会修正源点(x/1)到4和到6的最短距离。

    下图圆形为已遍历点,方形为未遍历的集合数据,实线为相邻连线,虚线为修正过程。

    PS:mark是已经被找过从该点出发的相邻路径,修正在已知最短距离的情况下(u),进行辐射,也就相对于找了u的所有相邻路径来比较更新(!mark[i]&& dis[i]>dis[u]+net.arcs[u][i]),但他并未记录u辐射的路径中的相邻最短路径(需要大循环)。

    遍历第一个点——1的过程

     

    遍历点2的过程

    如果看懂了点个赞,给点小动力,谢谢啦~

    PS:最简单(代码量)实现寻找最短路径的弗洛伊德算法点这里

    展开全文
  • Dijkstra迪杰斯特拉算法C++实现

    万次阅读 2016-04-22 22:13:49
    Dijkstra迪杰斯特拉算法C++实现

    Dijkstra迪杰斯特拉算法及C++实现

    Dijkstra算法是典型的最短路径路由算法,用来计算一个节点到其他所有节点的最短路径。算法的基本思想和流程是:
    1. 初始化出发点到其它各点的距离dist[]以及各点的前一个访问点pre[];
    2. for(i=2…n)
    {
    找出dist[]中未访问过点中的最小值,记录为best;
    以dist[best]为基准更新dist[];
    更新pre[];
    }
    一个有向图
    从1出发,第一次找到最小点2,更新dist[],然后找到最小点4,以此类推,以当前最小为最优(贪心算法),列出下表:

    迭代次数 s best dist[2] dist[3] dist[4] dist[5]
    1(初始化) {1} - 10 max 30 100
    2 {1,2} 2 10 60 30 100
    3 {1,2,4} 4 10 50 30 90
    4 {1,2,4,3} 3 10 50 30 60
    5 {1,2,4,3,5} 5 10 50 30 60

    具体实现:

    #include <iostream>
    #include <vector>
    const int maxdist = 9999;
    using namespace std;
    /*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/
    void Dijkstra(int n, int v, vector<int> &dist, vector<int> &pre, vector<vector<int>> &d)
    {
        vector<bool> s(n+1);
        for (int i = 1; i <= n;i++)
        {
            dist[i] = d[v][i];
            if (dist[i] < maxdist)
                pre[i] = v;
            else
                pre[i] = 0;
        }
        dist[v] = 0;
        s[v] = true;
        for (int i = 2; i <= n;i++)//总的迭代次数
        {
            int best = v;
            int temp = maxdist;
            for (int j = 1; j <= n;j++)//找到最小的距离
            {
                if (!s[j]&&dist[j]<temp)
                {
                    temp = dist[j];
                    best = j;
                }
            }
            s[best] = true;
            for (int j = 1; j <= n;j++)//更新dist和pre
            {
                if (!s[j] && d[best][j] != maxdist)
                {
                    int newdist = dist[best] + d[best][j];
                    if (newdist<dist[j])
                    {
                        dist[j] = newdist;
                        pre[j] = best;
                    }
                }
            }       
        }
    }
    
    void printpath(vector<int> pre, int init, int fina)
    {
        int temp=fina;
        vector<int> t;
        while (temp != init)
        {
            t.push_back(temp);
            temp = pre[fina];
            fina = temp;
        }
        cout << init << "->";
        for (int i = t.size(); i >1;i--)
        {
            cout << t[i-1] << "->";
        }
        cout << t[0];
        t.clear();
    }
    int main()
    {
        int n, l;
        cout << "请输入结点数和线数:";
        cin >> n >> l;
        vector<vector<int>> d(n+1, vector<int>(n+1));
        for (int i = 1; i <= n;i++)
        {
            for (int j = 1; j <= n; j++)
                d[i][j] = maxdist;
        }
        int p, q, len;
        for (int i = 1; i <= l; ++i)
        {
            cin >> p >> q >> len;
            if (len < d[p][q])       // 有重边
            {
                d[p][q] = len;      // p指向q
                d[q][p] = len;      // q指向p,这样表示无向图
            }
        }
        vector<int> dist(n+1),pre(n+1);
        for (int i = 1; i <= n; ++i)
            dist[i] = maxdist;
        Dijkstra(n, 1, dist, pre, d);
        cout << "点1到点n的最短路径长度: " << dist[n] << endl;
        cout << "点1到点n的路径为: ";
        printpath(pre, 1, n);
        return 0;
    }
    展开全文
  • 普里姆算法和迪杰斯特拉算法

    千次阅读 2018-01-27 14:54:21
    普里姆算法和迪杰斯特拉算法

    普里姆算法:

    普里姆算法不仅通过图构造生成树解决n个顶点之间的连通问题,同时使得总的耗费最小即最小代价生成树。
    首先简单讲解一下普里姆算法的思想,如下图:
    这里写图片描述

    首先第一张图为无向图,我们定义顶点1为初始点并且建立两个集合U和W,观察顶点1到其他顶点的距离,其中最短的是顶点3,因此将顶点1与顶点3之间连为实线,集合U中放入顶点3,W集中剩下2,4,5,6四个数;
    第二步观察U集中顶点1和顶点3分别到W集中各个顶点的距离,如U集中的顶点1到W集中的顶点2距离是6,但是U集中的顶点3到W集中的顶点2距离是5,5<6,因此留下顶点3和顶点2的虚线,以此类推,得到了第二张图;
    再次进行第一步找出权值最小的虚线画成实线,再次进行第二步,直到每一个顶点都被访问完结束。

    以下是c++的普里姆算法的代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    vector<int>A;
    int adjMatrix[100][100];
    int visited[100];
    int init = 1000;
    //用邻接矩阵存储图
    void createGraph(int nodeNum,int edgeNum) {
        //初始化邻接矩阵
        for (int i = 1; i <= nodeNum; i++) {
            for (int j = 1; j <= nodeNum; j++) {
                if (i == j) {
                    adjMatrix[i][j] = 0;
                }
                else
                {
                    adjMatrix[i][j] = init;
                }
            }
        }
        for (int k = 1; k <= edgeNum; k++) {
            int p1, p2,weight;
            cout << "请输入第" << k << "条边的两个顶点以及权重:";
            cin >> p1 >> p2 >> weight;
            adjMatrix[p1][p2] = weight;
            adjMatrix[p2][p1] = weight;
        }
        cout << "图邻接矩阵:" << endl;
        for (int i = 1; i <= nodeNum; i++) {
            for (int j = 1; j <= nodeNum; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
    //普里姆算法
    void primAlgorithm(int nodeNum) {
        int dis[100];
        //初始化第一行dis矩阵
        for (int i = 1; i <= nodeNum; i++) {
            dis[i] = adjMatrix[1][i];
        }
        visited[1] = 1;
        int count = 1;
        int sum = 0; 
        A.push_back(1);
        int j;
        while (count < nodeNum) {
            int min = init;
            //寻找最小权值顶点
            for (int i = 1; i <= nodeNum; i++) {
                if (visited[i] == 0 && dis[i] < min) {
                    min = dis[i];
                    j = i;
                }
            }
            visited[j] = 1;
            count++;
            sum = sum + dis[j];
            A.push_back(j);
            //更新dis矩阵
            for (int i = 1; i <= nodeNum; i++) {
                if (visited[i] == 0 && dis[i] > adjMatrix[j][i]) {
                    dis[i] = adjMatrix[j][i];
                }
            }
        }
        cout << "集合U中的顶点存放顺序:";
        for (int i = 0; i < A.size()-1; i++) {
            cout << A[i] << "->";
        }
        cout << A[A.size() - 1];
        cout << endl;
        cout <<"最小权重和="<< sum << endl;
    }
    void main() {
        int nodeNum, edgeNum;
        cout << "请输入图顶点个数=";
        cin >> nodeNum;
        cout << "请输入图边数=";
        cin >> edgeNum;
        createGraph(nodeNum,edgeNum);
        primAlgorithm(nodeNum);
    }

    程序运行结果:
    这里写图片描述


    迪杰斯特拉算法:

    迪杰斯特拉算法解决的是单源最短路径,给定一个带权有向图D与源点v,求从v到D中其他顶点的最短路径。
    具体做法:
    设集合S存放一级钢求出的最短路径的终点,初始状态时,集合S中只有一个源点,设为v0,以后求得一条(v0,…….vk),就将vk加入到集合S中,直到全部的顶点都加入到集合S中,算法结束。为了当前找到的从源点v0到其他终点vi的最短路径长度,引入了一个dis[i]矩阵,该矩阵的每一个值表示从源点v0到终点vi的最短路径的长度。如下图所示:
    这里写图片描述

    首先第一步将初始源点设为顶点1,因此问题就是顶点1到各个其他顶点的距离最短,从第一张有向图中可以得到最短的顶点1和顶点2,因此将顶点1和顶点2放入集合S中;
    第二步找源点1到终点3的距离,顶点1到顶点3的距离是无穷大,但是如果经过顶点2到达顶点3则距离是3+25=28,但是如果经过顶点4再到达顶点3则距离是3+8+4=15,因此迪杰斯特拉选择先经过顶点4再到达顶点3,因此在S集中放入4,再放入3,最短距离是15;
    第三步找源点1到终点5的距离,直接顶点1到顶点5的距离是30,如果经过顶点3再到顶点5的距离是3+8+4+10=25,如果是经过4到达5则距离为3+8+12=23,因此选择最后一条线路;

    以下是c++的迪杰斯特拉算法的代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    vector<int>A;
    int adjMatrix[100][100];
    int visited[100];
    int init = 1000;
    //用邻接矩阵存储图
    void createGraph(int nodeNum,int edgeNum) {
        //初始化邻接矩阵
        for (int i = 1; i <= nodeNum; i++) {
            for (int j = 1; j <= nodeNum; j++) {
                if (i == j) {
                    adjMatrix[i][j] = 0;
                }
                else
                {
                    adjMatrix[i][j] = init;
                }
            }
        }
        for (int k = 1; k <= edgeNum; k++) {
            int p1, p2,weight;
            cout << "请输入第" << k << "条边的两个顶点以及权重:";
            cin >> p1 >> p2 >> weight;
            adjMatrix[p1][p2] = weight;
            //adjMatrix[p2][p1] = weight;
        }
        cout << "图邻接矩阵:" << endl;
        for (int i = 1; i <= nodeNum; i++) {
            for (int j = 1; j <= nodeNum; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
    //迪杰斯特拉
    void dijkstraAlgorithm(int nodeNum) {
        int dis[100];
        //初始化第一行dis矩阵
        for (int i = 1; i <= nodeNum; i++) {
            dis[i] = adjMatrix[1][i];
        }
        visited[1] = 1;
        int count = 1;
        int sum = 0;
        int j;
        while (count < nodeNum) {
            int min = init;
            for (int i = 1; i <= nodeNum; i++) {
                if (visited[i] == 0 && dis[i] < min) {
                    min = dis[i];
                    j = i;
                }
            }
            visited[j] = 1;
            count++;
            //sum = sum + dis[j];
            sum = dis[j];
            cout << "从顶点1" << "->"<<"顶点"<< j << "最短路劲长度=" << sum << endl;
            for (int i = 1; i <= nodeNum; i++) {
                if (visited[i] == 0 && dis[i] > adjMatrix[j][i]+dis[j]) {
                    dis[i] = adjMatrix[j][i]+dis[j];
                }
            }
        }
    }
    void main() {
        int nodeNum, edgeNum;
        cout << "请输入图顶点个数=";
        cin >> nodeNum;
        cout << "请输入图边数=";
        cin >> edgeNum;
        createGraph(nodeNum,edgeNum);
        //primAlgorithm(nodeNum);
        dijkstraAlgorithm(nodeNum);
    }

    程序运行结果:
    这里写图片描述

    展开全文
  • 迪杰斯特拉算法

    2018-12-26 00:29:22
    1.对于给出的无向图/有向图,我们可以固定一点为原点:0 2.首先要有两个数组 一个用于存储两点间的距离(边),另一个数组用于存放当前点的前一个点 parent 3.在当前位置distance值不为无穷的情况下,通过循环比较...

    本文以Java实现迪杰特斯拉算法

    文末附上完整代码以及 测试样例

    主要思想:

    1.对于给出的无向图/有向图,我们可以固定一点为原点:0

    2.首先要有两个数组 一个用于存储两点间的距离(边),另一个数组用于存放当前点的前一个点 parent

    3.在当前位置distance值不为无穷的情况下,通过循环比较 (distance[i] + matrix[i][j]) < distance[j] )

    4.若满足则进行交换 //注以交换后相应的,改变其parent[]的值即可实现

    具体解析参照:https://www.bilibili.com/video/av2975983/?p=65

    实现代码如下:

    
    /*
     * Min最短路径
     */
    public void search() {
    	initialize();
    	for (int i = 0; i < distance.length; i++) {
    		for (int j = 0 ; j < distance.length ; j++ ){
    				if ( matrix[i][j] != Integer.MAX_VALUE ){
    					if ( distance[j] == Integer.MAX_VALUE ) {//如果当前值为无穷 则可以直接替换
    						parent[j] = i;
    						distance[j] = distance[i] + matrix[i][j]; 
    						//若替换则更变其前一个节点的指向
    						changParentDistance(j);
    					}else {
    						//在当前已经有之的情况下,比较厚进行替换
    						if ( (distance[i] + matrix[i][j]) < distance[j] ) {
    							parent[j] = i;
    							distance[j] = distance[i] + matrix[i][j];  
    							//若替换则更变其前一个节点的指向
    							changParentDistance(j);
    						}
    					}
    				}
    		}
    		flag[i] = true;
    	}
    }
    
    /*
     * 由于 j 的distance发生了变化
     * 更新前去为j的节点的distance
     */
    private void changParentDistance(int j){
    	for (int i = 0 ; i < distance.length ; i++ ){
    		if ( parent[i] == j && parent[i] != 0 ) {
    			distance[i] = distance[j] + matrix[j][i];//注意此处i,j代表的意义与上面不同
    		}
    	}
    }

    注:在输入前要想将distance parent初始化

    完整代码如下:

    一、实现方法Dijkstra类

    public class Dijkstra {
    	//节点总个数
    	private int num ;
    	//一维数组
    	private int sign[] = new int[num];
    	//二维数组
    	private int matrix[][] = new int[num][num];
    	//栈 用于存储 过程经过的点
    	private Stack<Integer> point = new Stack<>();
    	//最短路径的顶点集
    	private Stack<Integer>[] ways = new Stack[num];
    	//存放个点的最短路径
    	private int distance[] = new int[num];
    	//标记当前节点的父母
    	private int parent[] = new int[num];
    	//标记是否已经找到最短路径
    	private boolean flag[] = new boolean[num];
    	/**
    	 * 构造方法
    	 * @param sign
    	 * @param matrix
    	 */
    	public Dijkstra(int[] sign, int[][] matrix) {
    		super();
    		num = sign.length;
    		this.sign = sign;
    		this.matrix = matrix;
    		
    		//分配存储空间
    		ways = new Stack[num];
    		distance = new int[num];
    		parent = new int[num];
    		flag = new boolean[num];
    	}
    
    	/*
    	 * 简单搜索
    	 * 深度优先搜索
    	 */
    	public Stack<Integer> easyWay(int goal) {
    		int j = 0 ;
    		sign[0] =1 ;
    		point.push(0);
    		do {
    			for( int i = 0 ; i < sign.length ; i ++ ){
    				if ( matrix[j][i] == 1 && sign[i] != 1 ){
    					sign[i] = 1 ;
    					point.push(i) ;
    					j = i ;
    					break ;
    				}
    				if ( ( i + 1 ) == sign.length ) {
    					j = point.pop();
    				}
    			}
    		} while ( j != goal );
    		clarSign();//清空访问记录
    		return point;
    	}
    	
    	/*
    	 * Min最短路径
    	 */
    	public void search() {
    		initialize();
    		for (int i = 0; i < distance.length; i++) {
    			for (int j = 0 ; j < distance.length ; j++ ){
    					if ( matrix[i][j] != Integer.MAX_VALUE ){
    						if ( distance[j] == Integer.MAX_VALUE ) {//如果当前值为无穷 则可以直接替换
    							parent[j] = i;
    							distance[j] = distance[i] + matrix[i][j]; 
    							//若替换则更变其前一个节点的指向
    							changParentDistance(j);
    						}else {
    							//在当前已经有之的情况下,比较厚进行替换
    							if ( (distance[i] + matrix[i][j]) < distance[j] ) {
    								parent[j] = i;
    								distance[j] = distance[i] + matrix[i][j];  
    								//若替换则更变其前一个节点的指向
    								changParentDistance(j);
    							}
    						}
    					}
    			}
    			flag[i] = true;
    		}
    	}
    	
    	/*
    	 * 由于 j 的distance发生了变化
    	 * 更新前去为j的节点的distance
    	 */
    	private void changParentDistance(int j){
    		for (int i = 0 ; i < distance.length ; i++ ){
    			if ( parent[i] == j && parent[i] != 0 ) {
    				distance[i] = distance[j] + matrix[j][i];//注意此处i,j代表的意义与上面不同
    			}
    		}
    	}
    	
    	/*
    	 * 最短路径开始前的
    	 * 初始化
    	 */
    	private void initialize(){
    		for (int i = 0; i < flag.length; i++) {
    			flag[i] = false;
    			parent[i] = 0 ;
    			distance[i] = Integer.MAX_VALUE;//设置厨师最短路径均为最大
    			distance[0] = 0;
    		}
    	}
    	
    	/*
    	 * q清空访问记录
    	 */
    	public void clarSign() {
    		for (int i = 0; i < sign.length; i++) {
    			sign[i] = 0 ;
    		}
    	}
    	
    	public int[] getSign() {
    		return sign;
    	}
    
    	public void setSign(int[] sign) {
    		this.sign = sign;
    	}
    
    	public int[][] getMatrix() {
    		return matrix;
    	}
    
    	public void setMatrix(int[][] matrix) {
    		this.matrix = matrix;
    	}
    
    	public int getNum() {
    		return num;
    	}
    
    	public void setNum(int num) {
    		this.num = num;
    	}
    
    	public Stack<Integer> getPoint() {
    		return point;
    	}
    
    	public void setPoint(Stack<Integer> point) {
    		this.point = point;
    	}
    
    	public Stack<Integer>[] getWays() {
    		return ways;
    	}
    
    	public void setWays(Stack<Integer>[] ways) {
    		this.ways = ways;
    	}
    
    	public int[] getDistance() {
    		return distance;
    	}
    
    	public void setDistance(int[] distance) {
    		this.distance = distance;
    	}
    
    	public int[] getParent() {
    		return parent;
    	}
    
    	public void setParent(int[] parent) {
    		this.parent = parent;
    	}
    
    	public boolean[] getFlag() {
    		return flag;
    	}
    
    	public void setFlag(boolean[] flag) {
    		this.flag = flag;
    	}
    	
    }
    

    二、测试类:Main

    public class Main {
    	public static void main(String[] args) {
    		int sign[] = {0,0,0,0};
    		int matrix[][] = {
    				{0,1,1,1},
    				{1,0,1,0},
    				{1,1,0,1},
    				{1,0,1,0}
    		};
    		Dijkstra buildingPicture = new Dijkstra(sign, matrix);
    		Stack<Integer> point = buildingPicture.easyWay(2);
    		int j = -1 ;
    		while ( j != 0 ){
    			System.out.print( (j = point.pop()) + " <-- " );
    		}
    		System.out.println( "开始" );
    
    		/**
    		 * 无向图
    		 */
    		int sign_2[] = {0,0,0,0,0,0,0,0,0};
    		int matrix_2[][] = {
    				{0,1,5,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
    				{1,0,3,7,5,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
    				{5,3,0,Integer.MAX_VALUE,1,7,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
    				{Integer.MAX_VALUE,7,Integer.MAX_VALUE,0,2,Integer.MAX_VALUE,3,Integer.MAX_VALUE,Integer.MAX_VALUE},
    				{Integer.MAX_VALUE,5,1,2,0,3,6,9,Integer.MAX_VALUE},
    				{Integer.MAX_VALUE,Integer.MAX_VALUE,7,Integer.MAX_VALUE,3,0,Integer.MAX_VALUE,5,Integer.MAX_VALUE},
    				{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,6,Integer.MAX_VALUE,0,2,7},
    				{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,9,5,2,0,4},
    				{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,7,4,0}
    		};
    		Dijkstra buildingPicture2 = new Dijkstra(sign_2, matrix_2);
            buildingPicture2.search();
    		int distance[] = buildingPicture2.getDistance();
            for ( int i = 0 ; i < distance.length ; i++ ){
            	System.out.print( "点 i:" + distance[i] + "    ");
            }
            System.out.println();
            //获得最后一个节点 
            //最后通过倒序输出
            int last = distance.length-1;
            int parent[] = buildingPicture2.getParent();
            while ( last != 0 ){
            	System.out.print(last + " ");
            	last = parent[last];
            }
            System.out.println(last);
    	} 
    
    
    }
    

    测试结果:

    //第0点 到其它点的最短距离

    展开全文
  • Dijkstra 算法(中文名:迪杰斯特拉算法)是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他算法的一个子模块。举例来说,如果中的顶点表示城市,而边上的权重表示城市间开车...
  • 1,迪杰斯特拉算法介绍 迪杰斯特拉算法是典型最短路径算法,用于计算或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心外,层层扩展,直到扩展覆盖所有顶点。 2,迪杰斯特拉算法思想...
  • /**************************************************************************/ /* 算法实现作者:xingzhou */ /* 完成时间:2018/2/4
  • 数据结构——迪杰斯特拉算法

    千次阅读 2018-02-14 23:10:01
    当初学习数据结构的课件找不到了,就在网上找了两张图片,有一个有权无向图以及迪杰斯特拉算法的原理思想。以下是C++实现代码:#include&lt;iostream&gt; #include&lt;limits.h&gt; #define MAXVEX...
  • 点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。转自景禹今天我们主要看一个最短路径算法,迪杰斯特拉算法(Dijkstra Algorithm)( 计算从某个源点到其他...
  • 理解了好几天的最短路,今天有点眉目了 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!...
  • Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历...
  • (七)1.2_迪杰斯特拉算法求最短路径

    千次阅读 2020-06-27 13:09:52
    一:迪杰斯特拉算法   假如以顶点v1起点,用迪杰斯特拉算法求起点分别到顶点v2,v3,v4,v5的最短路初始我们计算出起点到各个顶点的最短路径,然后连接路径是所有路径中最短的那个顶点(加入到S集),然后接着重复这样的...
  • 储存结构,结构体的定义:(权值w...typedef struct ENode//的邻接表定义 { int adjVex;//任意顶点u相邻接的顶点 int w;//边的权值 struct ENode* nextArc;//指向下一个边结点 }ENode; typedef struct LG...
  • #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #define MaxSize 100 #define INF 1000001 typedef struct EageTable ... struct Ea...
  • Dijkstra算法及其C++实现 什么是最短路径问题 如果从中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 单源最短路径问题是指对于...
  • #include &lt;iostream&gt; #define MAXVEX 5 //结点数(初始默认6顶点,更改的话直接在这里修改即可) #define MAXEDGE 8 //边数(初始默认10条边,更改的话直接...//下面代码是有向图的邻接矩阵(某顶点到...
  • dijkstra算法详解(迪杰斯特拉算法)~~简单易懂 PS:此算法不能用于求负权,要求所有边的权重都为非负值。 一、简介(百度百科) 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又...
  •  最短路径的常用解法有迪杰斯特拉算法Dijkstra Algorithm, 弗洛伊德算法Floyd-Warshall Algorithm, 和贝尔曼福特算法Bellman-Ford Algorithm,其中,Floyd算法是多源最短路径,即求任意点到任意点到最短路径,而...
1 2 3 4 5 ... 20
收藏数 653
精华内容 261
关键字:

c++ 无向图 迪杰斯特拉算法