最短路径 订阅
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 展开全文
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
信息
性    质
一类经典算法问题
外文名
shortest path
解决思路
由已知点/边向外扩展
中文名
最短路径
解决方法
SPFA算法、Dijkstra算法等
最短路径最短路径介绍
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 [1]  确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。全局最短路径问题 - 求图中所有的最短路径。
收起全文
精华内容
参与话题
问答
  • 最短路径问题---Dijkstra算法详解

    万次阅读 多人点赞 2017-03-08 16:42:46
    前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ...从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法:...

    前言
    Nobody can go back and start a new beginning,but anyone can start today and make a new ending.
    Name:Willam
    Time:2017/3/8

    1、最短路径问题介绍

    问题解释:
    从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

    解决问题的算法:

    这篇博客,我们就对Dijkstra算法来做一个详细的介绍

    2、Dijkstra算法介绍

    • 算法特点:

      迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    • 算法的思路

      Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
      然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
      然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
      然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

    3、Dijkstra算法示例演示

    下面我求下图,从顶点v1到其他各个顶点的最短路径

    这里写图片描述

    首先第一步,我们先声明一个dis数组,该数组初始化的值为:
    这里写图片描述

    我们的顶点集T的初始化为:T={v1}

    既然是求 v1顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后,dis[2](下标从0开始)的值就已经从“估计值”变为了“确定值”,即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。
    为什么呢?因为目前离 v1顶点最近的是 v3顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

    OK,既然确定了一个顶点的最短路径,下面我们就要根据这个新入的顶点V3会有出度,发现以v3 为弧尾的有: < v3,v4 >,那么我们看看路径:v1–v3–v4的长度是否比v1–v4短,其实这个已经是很明显的了,因为dis[3]代表的就是v1–v4的长度为无穷大,而v1–v3–v4的长度为:10+50=60,所以更新dis[3]的值,得到如下结果:
    这里写图片描述

    因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3],通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想:通过“边”来松弛v1顶点到其余各个顶点的路程。

    然后,我们又从除dis[2]和dis[0]外的其他值中寻找最小值,发现dis[4]的值最小,通过之前是解释的原理,可以知道v1到v5的最短距离就是dis[4]的值,然后,我们把v5加入到集合T中,然后,考虑v5的出度是否会影响我们的数组dis的值,v5有两条出度:< v5,v4>和 < v5,v6>,然后我们发现:v1–v5–v4的长度为:50,而dis[3]的值为60,所以我们要更新dis[3]的值.另外,v1-v5-v6的长度为:90,而dis[5]为100,所以我们需要更新dis[5]的值。更新后的dis数组如下图:
    这里写图片描述

    然后,继续从dis中选择未确定的顶点的值中选择一个最小的值,发现dis[3]的值是最小的,所以把v4加入到集合T中,此时集合T={v1,v3,v5,v4},然后,考虑v4的出度是否会影响我们的数组dis的值,v4有一条出度:< v4,v6>,然后我们发现:v1–v5–v4–v6的长度为:60,而dis[5]的值为90,所以我们要更新dis[5]的值,更新后的dis数组如下图:
    这里写图片描述

    然后,我们使用同样原理,分别确定了v6和v2的最短路径,最后dis的数组的值如下:
    这里写图片描述

    因此,从图中,我们可以发现v1-v2的值为:∞,代表没有路径从v1到达v2。所以我们得到的最后的结果为:

    起点  终点    最短路径    长度
    v1    v2     无          ∞    
          v3     {v1,v3}    10
          v4     {v1,v5,v4}  50
          v5     {v1,v5}    30
          v6     {v1,v5,v4,v6} 60
    

    4、Dijkstra算法的代码实现(c++)

    • Dijkstra.h文件的代码
    /************************************************************/
    /*                程序作者:Willam                          */
    /*                程序完成时间:2017/3/8                    */
    /*                有任何问题请联系:2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    #pragma once
    //#pragma once是一个比较常用的C/C++杂注,
    //只要在头文件的最开始加入这条杂注,
    //就能够保证头文件只被编译一次。
    
    #include<iostream>
    #include<string>
    using namespace std;
    
    /*
    本程序是使用Dijkstra算法实现求解最短路径的问题
    采用的邻接矩阵来存储图
    */
    //记录起点到每个顶点的最短路径的信息
    struct Dis {
        string path;
        int value;
        bool visit;
        Dis() {
            visit = false;
            value = 0;
            path = "";
        }
    };
    
    class Graph_DG {
    private:
        int vexnum;   //图的顶点个数
        int edge;     //图的边数
        int **arc;   //邻接矩阵
        Dis * dis;   //记录各个顶点最短路径的信息
    public:
        //构造函数
        Graph_DG(int vexnum, int edge);
        //析构函数
        ~Graph_DG();
        // 判断我们每次输入的的边的信息是否合法
        //顶点从1开始编号
        bool check_edge_value(int start, int end, int weight);
        //创建图
        void createGraph();
        //打印邻接矩阵
        void print();
        //求最短路径
        void Dijkstra(int begin);
        //打印最短路径
        void print_path(int);
    };
    
    • Dijkstra.cpp文件的代码
    #include"Dijkstra.h"
    
    //构造函数
    Graph_DG::Graph_DG(int vexnum, int edge) {
        //初始化顶点数和边数
        this->vexnum = vexnum;
        this->edge = edge;
        //为邻接矩阵开辟空间和赋初值
        arc = new int*[this->vexnum];
        dis = new Dis[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) {
            arc[i] = new int[this->vexnum];
            for (int k = 0; k < this->vexnum; k++) {
                //邻接矩阵初始化为无穷大
                    arc[i][k] = INT_MAX;
            }
        }
    }
    //析构函数
    Graph_DG::~Graph_DG() {
        delete[] dis;
        for (int i = 0; i < this->vexnum; i++) {
            delete this->arc[i];
        }
        delete arc;
    }
    
    // 判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool Graph_DG::check_edge_value(int start, int end, int weight) {
        if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
            return false;
        }
        return true;
    }
    
    void Graph_DG::createGraph() {
        cout << "请输入每条边的起点和终点(顶点编号从1开始)以及其权重" << endl;
        int start;
        int end;
        int weight;
        int count = 0;
        while (count != this->edge) {
            cin >> start >> end >> weight;
            //首先判断边的信息是否合法
            while (!this->check_edge_value(start, end, weight)) {
                cout << "输入的边的信息不合法,请重新输入" << endl;
                cin >> start >> end >> weight;
            }
            //对邻接矩阵对应上的点赋值
            arc[start - 1][end - 1] = weight;
            //无向图添加上这行代码
            //arc[end - 1][start - 1] = weight;
            ++count;
        }
    }
    
    void Graph_DG::print() {
        cout << "图的邻接矩阵为:" << endl;
        int count_row = 0; //打印行的标签
        int count_col = 0; //打印列的标签
        //开始打印
        while (count_row != this->vexnum) {
            count_col = 0;
            while (count_col != this->vexnum) {
                if (arc[count_row][count_col] == INT_MAX)
                    cout << "∞" << " ";
                else
                cout << arc[count_row][count_col] << " ";
                ++count_col;
            }
            cout << endl;
            ++count_row;
        }
    }
    void Graph_DG::Dijkstra(int begin){
        //首先初始化我们的dis数组
        int i;
        for (i = 0; i < this->vexnum; i++) {
            //设置当前的路径
            dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
            dis[i].value = arc[begin - 1][i];
        }
        //设置起点的到起点的路径为0
        dis[begin - 1].value = 0;
        dis[begin - 1].visit = true;
    
        int count = 1;
        //计算剩余的顶点的最短路径(剩余this->vexnum-1个顶点)
        while (count != this->vexnum) {
            //temp用于保存当前dis数组中最小的那个下标
            //min记录的当前的最小值
            int temp=0;
            int min = INT_MAX;
            for (i = 0; i < this->vexnum; i++) {
                if (!dis[i].visit && dis[i].value<min) {
                    min = dis[i].value;
                    temp = i;
                }
            }
            //cout << temp + 1 << "  "<<min << endl;
            //把temp对应的顶点加入到已经找到的最短路径的集合中
            dis[temp].visit = true;
            ++count;
            for (i = 0; i < this->vexnum; i++) {
                //注意这里的条件arc[temp][i]!=INT_MAX必须加,不然会出现溢出,从而造成程序异常
                if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
                    //如果新得到的边可以影响其他为访问的顶点,那就就更新它的最短路径和长度
                    dis[i].value = dis[temp].value + arc[temp][i];
                    dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
                }
            }
        }
    
    }
    void Graph_DG::print_path(int begin) {
        string str;
        str = "v" + to_string(begin);
        cout << "以"<<str<<"为起点的图的最短路径为:" << endl;
        for (int i = 0; i != this->vexnum; i++) {
            if(dis[i].value!=INT_MAX)
            cout << dis[i].path << "=" << dis[i].value << endl;
            else {
                cout << dis[i].path << "是无最短路径的" << endl;
            }
        }
    }
    • main.cpp文件的代码
    #include"Dijkstra.h"
    
    
    //检验输入边数和顶点数的值是否有效,可以自己推算为啥:
    //顶点数和边数的关系是:((Vexnum*(Vexnum - 1)) / 2) < edge
    bool check(int Vexnum, int edge) {
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;
    }
    int main() {
        int vexnum; int edge;
    
        cout << "输入图的顶点个数和边的条数:" << endl;
        cin >> vexnum >> edge;
        while (!check(vexnum, edge)) {
            cout << "输入的数值不合法,请重新输入" << endl;
            cin >> vexnum >> edge;
        }
        Graph_DG graph(vexnum, edge);
        graph.createGraph();
        graph.print();
        graph.Dijkstra(1);
        graph.print_path(1);
        system("pause");
        return 0;
    }

    输入:

    6 8
    1 3 10
    1 5 30
    1 6 100
    2 3 5
    3 4 50
    4 6 10
    5 6 60
    5 4 20

    输出:
    这里写图片描述

    从输出可以看出,程序的结果和我们之前手动计算的结果是一样的。

    展开全文
  • 最短路径: 在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。 DiskStra算法: 求单源最短路径,即求一个顶点到...

    最短路径:

    在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。

    DiskStra算法:

    求单源最短路径,即求一个顶点到任意顶点的最短路径,其时间复杂度为O(V*V)

    如图所示:求顶点0到各顶点之间的最短路径

    代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVexNum 50
    #define MaxInt 32767
    #define MaxEdgeNum 50
    //邻接矩阵
    typedef int VertexType;
    typedef int EdgeType;
    typedef struct AMGraph{
    	VertexType vexs[MaxVexNum];//顶点表 
    	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
    	int vexnum,edgenum;//顶点数,边数 
    }AMGraph; 
    
    void createGraph(AMGraph &g){//创建无向图 
    	printf("请输入顶点数:");
    	scanf("%d",&g.vexnum);
    	printf("\n请输入边数:");
    	scanf("%d",&g.edgenum);
    	
    	//初始化顶点表 
    	for(int i=0;i<g.vexnum;i++){
    		g.vexs[i]=i; 
    	} 
    	for(int i=0;i<g.vexnum;i++){
    		for(int j=0;j<g.vexnum;j++){
    			g.arcs[i][j]=MaxInt;
    			if(i==j) g.arcs[i][j]=0;
    		}
    	} 
    	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
    	for(int i=0;i<g.edgenum;i++){
    		int x,y,w;
    		scanf("%d%d%d",&x,&y,&w);
    		g.arcs[x][y]=w;
    		//g.arcs[y][x]=w;
    	}
    }
    void PrintGraph(AMGraph g){
    	printf("邻接矩阵为:\n");
    	for(int i=0;i<g.vexnum;i++) {
    		printf("  %d",g.vexs[i]);
    	}
    	printf("\n");
    	for(int i=0;i<g.vexnum;i++){
    		printf("%d ",g.vexs[i]);
    		for(int j=0;j<g.vexnum;j++){
    			if(g.arcs[i][j]==32767){
    				printf("∞ "); 
    			}else{
    				printf("%d  ",g.arcs[i][j]);
    			}	
    		}
    		printf("\n");
    	} 
    }
    //Dijkstra算法,求单源最短路径
    void Dijkstra(AMGraph g,int dist[],int path[],int v0){
    	int n=g.vexnum,v;
    	int set[n];//set数组用于记录该顶点是否归并 
    	//第一步:初始化 
    	for(int i=0;i<n;i++){
    		set[i]=0;
    		dist[i]=g.arcs[v0][i];
    		if(dist[i]<MaxInt){//若距离小于MaxInt说明两点之间有路可通 
    			path[i]=v0;//则更新路径i的前驱为v 
    		}else{
    			path[i]=-1; //表示这两点之间没有边
    		 } 
    	}
    	set[v0]=1;//将初始顶点并入 
    	path[v0]=-1;//初始顶点没有前驱
    	
    	//第二步 
    	for(int i=1;i<n;i++){//共n-1个顶点 
    		int min=MaxInt;
    		//第二步:从i=1开始依次选一个距离顶点的最近顶点 
    		for(int j=0;j<n;j++){
    			if(set[j]==0&&dist[j]<min){
    				v=j;
    				min=dist[j];
    		}
    	}
    	//将顶点并入 
    	set[v]=1;	
    	//第三步:在将新结点并入后,其初始顶点v0到各顶点的距离将会发生变化,所以需要更新dist[]数组
    	for(int j=0;j<n;j++){
    		if(set[j]==0&&dist[v]+g.arcs[v][j]<dist[j]){
    			dist[j]=dist[v]+g.arcs[v][j];
    			path[j]=v;
    		}
    	} 	
     } 
     //输出 
     printf("       ");
     for(int i=0;i<n;i++) printf("%d  ",i);
      
     printf("\ndist[]:");
     for(int i=0;i<n;i++) printf("%d  ",dist[i]);
     
     printf("\npath[]:");
     for(int i=0;i<n;i++) printf("%d  ",path[i]);
    
    }
    
    int main(){
    	AMGraph g;
    	createGraph(g);
    	int dist[g.vexnum];
    	int path[g.vexnum];
    	Dijkstra(g,dist,path,0);
    } 

    Floyd算法:

    求各顶点之间的最短路径,其时间复杂度为O(V*V*V)

    如图所示,求<1,0>之间的最短路径:

    代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVexNum 50
    #define MaxInt 32767
    #define MaxEdgeNum 50
    //邻接矩阵
    typedef int VertexType;
    typedef int EdgeType;
    typedef struct AMGraph{
    	VertexType vexs[MaxVexNum];//顶点表 
    	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
    	int vexnum,edgenum;//顶点数,边数 
    }AMGraph; 
    
    void createGraph(AMGraph &g){//创建无向图 
    	printf("请输入顶点数:");
    	scanf("%d",&g.vexnum);
    	printf("\n请输入边数:");
    	scanf("%d",&g.edgenum);
    	
    	//初始化顶点表 
    	for(int i=0;i<g.vexnum;i++){
    		g.vexs[i]=i; 
    	} 
    	for(int i=0;i<g.vexnum;i++){
    		for(int j=0;j<g.vexnum;j++){
    			g.arcs[i][j]=MaxInt;
    			if(i==j) g.arcs[i][j]=0;
    		}
    	} 
    	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
    	for(int i=0;i<g.edgenum;i++){
    		int x,y,w;
    		scanf("%d%d%d",&x,&y,&w);
    		g.arcs[x][y]=w;
    		//g.arcs[y][x]=w;
    	}
    }
    void PrintGraph(AMGraph g){
    	printf("邻接矩阵为:\n");
    	for(int i=0;i<g.vexnum;i++) {
    		printf("  %d",g.vexs[i]);
    	}
    	printf("\n");
    	for(int i=0;i<g.vexnum;i++){
    		printf("%d ",g.vexs[i]);
    		for(int j=0;j<g.vexnum;j++){
    			if(g.arcs[i][j]==32767){
    				printf("∞ "); 
    			}else{
    				printf("%d  ",g.arcs[i][j]);
    			}	
    		}
    		printf("\n");
    	} 
    }
    
    //Floyd算法
    
    //递归输出两个顶点直接最短路径 
    void printPath(int u,int v,int path[][MaxVexNum]){
    	if(path[u][v]==-1){
    		printf("[%d %d] ",u,v);
    	}else{
    		int mid=path[u][v];
    		printPath(u,mid,path);
    		printPath(mid,v,path);
    	}
    }
    void Floyd(AMGraph g,int path[][MaxVexNum]){
    	int n=g.vexnum;
    	int A[n][n];
    	//第一步:初始化path[][]和A[][]数组 
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			A[i][j]=g.arcs[i][j];
    			path[i][j]=-1; 
    		}
    	}
    	//第二步:三重循环,寻找最短路径 
    	for(int v=0;v<n;v++){//第一层是代表中间结点 
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				if(A[i][j]>A[i][v]+A[v][j]){
    					A[i][j]=A[i][v]+A[v][j];
    					path[i][j]=v;
    				}
    			}
    		} 
    	} 
    } 
     
    int main(){
    	AMGraph g;
    	createGraph(g);
    	PrintGraph(g);
    	int path[MaxVexNum][MaxVexNum];
    	Floyd(g,path);
    
    	printPath(1,0,path);
    } 

    代码运行截图:

    展开全文
  • 最短路径

    千次阅读 2014-07-20 10:38:09
    最短路径,数据结构,c,图,算法

    本文为原创:转载请注明来至http://blog.csdn.net/j903829182/article/details/37989633
    /*
    最短路径:
    1.在一个图中,若从一个顶点到另一个顶点存在着路径,则定义路径长度为一条路径上所有经过的边的数目。
      图中从一个顶点到另一个顶点可能存在多条路径,我们把路径长度最短的那条路径叫作最短路径,其路径长度叫做最短路径长度或最短距离
      在一个带权图中,若从一个顶点到另一个存在着一条路径,则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个顶点
      到另一个顶点可能存在着多条路径,我们把带权路径长度值最小的那条路径也叫作最短路径,其带权路径长度叫作最短路径长度或最短距离。


    2.狄克斯特拉算法:
      对于有向带权图中从一个确定顶点(称为源点)到其余各顶点的最短路径问题,狄克斯特拉(Dijkastra)提出了一个按路径长度递增的顺序逐步产生最短路径
      的构造方法。
      狄克斯特拉算法思想:设置两个顶点集合S和T,集合S中存放已找到最短路径的顶点,集合T中存放当前还未找到最短路径的顶点。初始状态时,集合
      S中只包含了源点,设为v0,然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中,集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余
      顶点的当前最短路径长度值,集合T中各顶点的新的当前最短路径值为原来的当前路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复,直到集合T
      中的顶点全部加入到集合S中为止。

    */

    #include<stdio.h>
    #include<malloc.h>
    #define MaxSize 10        //定义元素的大小
    typedef char DataType;        //定义一个类型
    #define MaxVertices 10       //定义顶点的最大值
    #define MaxWeight 10000        //定义无穷大的具体值
    typedef char VerT;
    
    typedef struct{     //定义一个结构体
      DataType list[MaxSize];
      int size;             //结构体元素的大小
    }SeqList;                 //结构体的对象
    
    typedef struct{
    
    	SeqList Vertices;//存放顶点的顺序表
    	int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵
    	int numOfEdges;//边的条数
    }AdjMGraph;
    
    
    typedef struct{
    
    	int row;//行下标
    	int col;//列下标
    	int weight;//权值
    }RowColWeight;//边信息结构体
    
    
    typedef struct{
    
    	VerT vertex;//保存最小生成树每条边的弧头顶点数据
    	int weight;//保存最小生成树的相应边的权值
    }MinSpanTree;
    
    //初始化
    void  initiate(SeqList *L){
          L->size=0;//定义初始化元素个数
    }
    
    //求当前元素的个数
    int getLength(SeqList L){
    
    	return L.size;//返回长度
    }
    
    //插入数据元素
    int insertData(SeqList *L,int i,DataType x){
    	//在顺序表L的第i(0<=i<=size)个位置前插入数据元素x
    	//插入成功返回1,出人失败返回0
       int j;
       if(L->size>=MaxSize){
          printf("顺序表已满,无法插入!!\n");
    	  return 0;
       }else if(i<0||i>L->size){
          printf("插入的位置不合法,不在指定的范围,参数i不合法!\n");
    	  return 0;
       }else{
          //从后向前一致移动数据,为插入做准备
    	   for(j=L->size;j>i;j--){
    	         L->list[j]=L->list[j-1];
    	   }
           L->list[i]=x;
    	   L->size++;
    	   return 1;
       }
    }
    
    //删除数据
    int deleteData(SeqList *L,int i,DataType *x){ 
        //删除顺序表中位置为i的数据i>=0&&i<=size-1,把数据保存到x中
    	//删除成功返回1,否则返回0
    	int j;
    	if(L->size<=0){
    	    printf("顺序表已空无数据元素可删!\n");
    		return 0;
    	}else if(i<0||i>L->size-1){
    	    printf("参数i不合法,不能删除!\n");
    		return 0;
    	}else{
    		*x=L->list[i];
    		for(j=i+1;j<=L->size-1;j++){//从前往后一次前移
    		     L->list[j-1]=L->list[j];
    		}
    		L->size--;//数据元素减一
    		return 1;
    	}
    }
    
    //取出数据元素
    int getData(SeqList L,int i,DataType *x){
        if(i<0||i>L.size-1){
    		printf("参数i不合法,不能删除!\n");
    		return 0;
    	}else{
    	    *x=L.list[i];
    		return 1;
    	}
    }
    
    
    
    //初始化有n个顶点的顺序表和邻接矩阵
    void InitiateG(AdjMGraph *g,int n){
    
    	//初始化
    	int i,j;
    	
    	for(i=0;i<n;i++){
    	
    		for(j=0;j<n;j++){
    			
    			if(i==j){
    			
    				g->edge[i][j]=0;
    			}else{
    			
    				g->edge[i][j]=MaxWeight;//MaxWeight表示无穷大
    			}
    		}
    	}
    
    	g->numOfEdges=0;//边的条数置为0
    	initiate(&g->Vertices);//顺序表初始化
    
    }
    
    
    //插入顶点
    void InsertVertex(AdjMGraph *g,DataType vertex){
    //在图G中插入顶点vertex
    
    	insertData(&g->Vertices,g->Vertices.size,vertex);//顺序表尾插入
    
    }
    
    
    //插入边
    void InsertEdge(AdjMGraph *g,int v1,int v2,int weight){
    //在图中插入边<v1,v2>,边<v1,v2>的权为weight
    	if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){
    	
    		printf("参数v1或v2越界出错!!!\n");
    		return ;
    	}
    
    	g->edge[v1][v2]=weight;
    	g->numOfEdges++;
    
    }
    
    
    //删除边
    void DeleteEdge(AdjMGraph *g,int v1,int v2){
    
    	//在G图中删除边<v1,v2>
    	if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){
    	
    		printf("参数v1或v2越界出错!!!\n");
    		return ;
    	}
    
    	if(g->edge[v1][v2]==MaxWeight||v1==v2){
    	
    		printf("该边不存在!!!\n");
    		return;
    	}
    
    
    	g->edge[v1][v2]=MaxWeight;
    	g->numOfEdges--;
    
    
    }
    
    
    //取第一个邻接顶点
    int GetFirstVex(AdjMGraph g,int v){
    //在图G中寻找序号为v的顶点的第一个邻接顶点
    	//如果这样的顶点存在,则返回该邻接顶点的序号,否则返回-1
    	int col;
    	if(v<0||v>=g.Vertices.size){
    	
    		printf("参数v1越界出错!!!\n");
    		return -1;
    	}
    
    	for(col=0;col<g.Vertices.size;col++){
    	
    		if(g.edge[v][col]>0&&g.edge[v][col]<MaxWeight){
    		
    			return col;
    		}
    	}
    
    	return -1;
    
    }
    
    
    //取下一个邻接顶点
    int GetNextVex(AdjMGraph g,int v1,int v2){
    //在图中寻找v1顶点的邻接顶点v2的下一个邻接顶点
    	//如果这样的邻接顶点存在,则返回该邻接顶点的序号;否则返回-1
    	//v1和v2都是相应的顶点的序号
    	int col;
    	if(v1<0||v1>g.Vertices.size||v2<0||v2>=g.Vertices.size){
    		printf("参数v1或v2越界出错!!!\n");
    		return -1;
    	}
    
    
    	for(col=v2+1;col<g.Vertices.size;col++){
    	
    		if(g.edge[v1][col]>0&&g.edge[v1][col]<MaxWeight){
    		
    			return col;
    		}
    	}
    
    	return -1;
    
    }
    
    
    void CreatGraph(AdjMGraph *g,DataType V[],int n,RowColWeight E[],int e){
    //在图中插入n个顶点信息V和e条边信息E
    	int i,k;
    	InitiateG(g,n);//d顶点顺序表初始化
    	for(i=0;i<n;i++){
    	
    		InsertVertex(g,V[i]);//插入顶点
    	}
    	for(k=0;k<e;k++){
    		InsertEdge(g,E[k].row,E[k].col,E[k].weight);//插入边
    	}
    }
    
    //普里姆函数设计
    //参数g为邻接矩阵存储结构的图
    //closeVertex为通过函数得到的最小生成树的顶点和相应顶点边的权值数据
    void Prim(AdjMGraph g,MinSpanTree closeVertex[]){
    	//用普里姆算法建立带权图G的最小生成树closeVertex
    	VerT x;
    	int n=g.Vertices.size,minCost;
    	int *lowCost=(int *)malloc(sizeof(int)*n);//保存集合U中顶点ui与集合V-U中顶点vj的所有边中当前具有最小权值的边(u,v)
    	int i,j,k;
    	for(i=1;i<n;i++){//初始化
    	//lowCost的初始值为邻接矩阵数组中第0行的值
    		lowCost[i]=g.edge[0][i];//存放了从集合U中顶点0到集合V-U中各个顶点的权值
    	}
    	//从顶点0出发构造最小生成树
    	getData(g.Vertices,0,&x);//取顶点0
    	closeVertex[0].vertex=x;//保存顶点
    	lowCost[0]=-1;//标记顶点
    	for(i=1;i<n;i++){
    	
    		//寻找当前最小权值的边对应的弧头顶点k
    		minCost=MaxWeight;//MaxWeight为定义的最大值
    		for(j=1;j<n;j++){
    		
    			if(lowCost[j]<minCost&&lowCost[j]>0){
    			
    				minCost=lowCost[j];
    				k=j;
    			}
    		}
    
    
    		getData(g.Vertices,k,&x);//取弧头顶点k
    		closeVertex[i].vertex=x;//保存弧头顶点k的数据
    		closeVertex[i].weight=minCost;//保存相应的权值
    		lowCost[k]=-1;//标志顶点k
    		//根据加入集合U的顶点k修改lowCost中的数值
    		for(j=1;j<n;j++){
    		
    			if(g.edge[k][j]<lowCost[j]){
    			
    				lowCost[j]=g.edge[k][j];
    			}
    		}
    
    	}
    
    }
    
    
    //狄克斯特拉算法函数的设计
    //函数共有4个参数,其中2个为输入参数,分别为带权图G和源点序号v0;两个为输出参数
    //分别为distance[]和path[],distance[]用来存放得到从源点v0到其余各顶点的最短距离数值
    //path[]用来存放得到的从源点v0到其余各顶点的最短路径上到目标顶点的前一顶点的下标
    void Dijkstra(AdjMGraph g,int v0,int distance[],int path[]){
    	//带权图G从下标v0顶点到其他顶点的最短距离distance和最短路径下标
    	int n=g.Vertices.size;
    	//s[i]=0表示顶点i在集合T中,s[i]=1表示顶点i已从集合T移到集合S中
    	int *s=(int *)malloc(sizeof(int)*n);
    	int minDis,i,j,u;
    	//初始化
    	for(i=0;i<n;i++){
    	
    		distance[i]=g.edge[v0][i];
    		s[i]=0;
    		if(i!=v0&&distance[i]<MaxWeight){
    		
    			path[i]=v0;
    		}else{
    		
    			path[i]=-1;
    		}
    	}
    
    	s[v0]=1;//标志顶点v0已从集合T加入到集合S中
        //在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u
    	for(i=1;i<n;i++){
    		minDis=MaxWeight;
    		for(j=0;j<n;j++){
    		
    			if(s[j]==0&&distance[j]<minDis){
    			
    				u=j;
    				minDis=distance[j];
    			}
    		}
    		//当已不在存在路径时,算法结束。此语句对非连通图是必需的
    		if(minDis==MaxWeight){
    		
    			return;
    		}
    
    		s[u]=1;//标志顶点u已经从集合T中加入到集合S中
    		//修改从v0到其他顶点的最短距离和最短路径
    		for(j=0;j<n;j++){
    		
    			if(s[j]==0&&g.edge[u][j]<MaxWeight&&
    				distance[u]+g.edge[u][j]<distance[j]){
    			
    				//顶点v0经顶点u到其他顶点的最短距离和最短路径
    				distance[j]=distance[u]+g.edge[u][j];
    				path[j]=u;
    			}
    		}
    	}
    
    }
    
    
    
    void main(){
    
    	/*
    	AdjMGraph g;
    	DataType a[]={'A','B','C','D','E','F','G'};
    	RowColWeight rcw[]={{0,1,50},{1,0,50},{0,2,60},{2,0,60},{1,3,65},
    	{3,1,65},{1,4,40},{4,1,40},{2,3,52},{3,2,52},{2,6,45},{6,2,45},
    	{3,4,50},{4,3,50},{3,5,30},{5,3,30},{3,6,42},{6,3,42},{6,2,45},
    	{4,5,70},{5,4,70}};
    	int n=7,e=20;
    	int i,j;
        MinSpanTree closeVertex[7];//定义保存最小生成树的数组
    
    	CreatGraph(&g,a,n,rcw,e);//创建图
        
        Prim(g,closeVertex);//调用Prim函数
    	//输出Prim函数得到最小生成树的顶点序列和权值
    	printf("初始顶点=%c\n",closeVertex[0].vertex);
        for(i=1;i<n;i++){
    	
    		printf("顶点=%c   边的权值=%d\n",closeVertex[i].vertex,closeVertex[i].weight);
    	}
    */
    
    
    	AdjMGraph g;
    	DataType a[]={'A','B','C','D','E','F'};
    	RowColWeight rcw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,15},
    	{2,5,7},{4,3,4},{5,3,10},{5,4,18}};
    	int i,n=6,e=9;
    	int distance[6],path[6];
    	CreatGraph(&g,a,n,rcw,e);//创建图
    	Dijkstra(g,0,distance,path);
    	printf("从顶点%c到其他各顶点的最短距离为:\n",g.Vertices.list[0]);
    	
    	for(i=0;i<n;i++){
    	
    		printf("到顶点%c的最短距离为%d\n",g.Vertices.list[i],distance[i]);
    	}
    
    	printf("\n从顶点%c到其他各顶点最短路径的前一顶点为:\n",g.Vertices.list[0]);
    	for(i=0;i<n;i++){
    	
    		if(path[i]!=-1){
    		
    			printf("到顶点%c的前一顶点为%c\n",
    				g.Vertices.list[i],g.Vertices.list[path[i]]);
    		}
    	}
    
    }
    














    展开全文
  • 关于单源最短路径的问题非常典型,这里没有给出分析与证明,仅仅给出了实现。 需要指出的是,许多实现仅给出了最短路径的长度,而没有给出“最短路径”,这里用给出了实现。 如程序中那样,定义一个数组p[N],其中...
  • 最短路径算法最短路径算法最短路径算法最短路径算法

空空如也

1 2 3 4 5 ... 20
收藏数 43,495
精华内容 17,398
关键字:

最短路径