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

Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，是广度优先算法的一种，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。 Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra 算法的时间复杂度为O(n^2)

空间复杂度取决于存储方式，邻接矩阵为O(n^2)

代码实现

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
#define INF 0x7fffffff
#define maxN 50
#define USE_C 1
#define NOT_USE_C 0
#define USE_CPP 1
int matrix[maxN][maxN];
void Dijkstra_cpp(vector<vector<int>>&vec,vector<int>& result,int v0){
  vector<int> visited(vec.size(),0);
  int last_visitied = 0;
  result[0] = 0;
  for(int i =0;i<vec.size()-1;i++){
    for(int j = 0;j<vec.size()-1;j++){
    if(visited[i]==0){
      if(vec[v0][j]!= 0){
      int dist =vec[v0][j] +last_visited;
      if(dist<result[j])
      result[j] = dist;
    }
  }
}
  int minIndex = 0;
  while(visited[minIndex] == 1)
    minIndex++;
  for(int j = minIndex;j<vec.size();j++){
    if(visited[j] ==0&&result[j]<result[minIndex]){
      minIndex = j;
    }
  }
  last_visited = result[minIndex];
  visited[minIndex] = 1;
  v0 = minIndex;
  }
}
int _tmain(int argc,_TCHAR* argv[]){
  freopen("Dijkstra2Data.txt","r",stdin);
  int n;
  cin>>n;
  vector<vector<int>> vec(n,vector<int>(n,0));
  for(i = 0;i<n;i++){
    for(j = 0;j<n;j++){
      cin>>vec[i][j];
    }
  }
  vector<int> result(n,INF);
  Dijkstra_cpp(vec,result,0);
  for(int i =0;i<n;i++){
    if(result[i] == INF)
    cout<<"INF"<<endl;
    else
    cout<<result[i]<<endl;
  }
  return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++用Dijkstra(迪杰斯特拉)算法求最短路径

    C++用Dijkstra(迪杰斯特拉)算法求最短路径

    算法介绍 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低. 算法思想 按路径长度递增次序产生算法: 把顶点集合V分成两组: (1)S:已求出的顶点的集合(初始时只含有源点V0) (2)V-S=T:尚未确定的顶点集合 将T中顶点按递增

  • Dijkstra算法最短路径的C++实现与输出路径

    Dijkstra算法最短路径的C++实现与输出路径

    某个源点到其余各顶点的最短路径 这个算法最开始心里怕怕的,不知道为什么,花了好长时间弄懂了,也写了一遍,又遇到时还是出错了,今天再次写它,心里没那么怕了,耐心研究,懂了之后会好开心的,哈哈 Dijkstra算法: 图G 如图:若要求从顶点1到其余各顶点的最短路径,该咋求: 迪杰斯特拉提出"按最短路径长度递增的次序"产生最短路径. 首先,在所有的这些最短路径中,长度最短的这条路径必定只有一条弧,且它的权值是从源点出发的所有弧上权的最小值,例如:在图G中,从源点1出发有3条弧,其中以弧(1

  • C++实现Dijkstra算法

    本文实例为大家分享了C++实现Dijkstra算法的具体代码,供大家参考,具体内容如下 #include <iostream> #include <limits> using namespace std; struct Node { //定义表结点 int adjvex; //该边所指向的顶点的位置 int weight;// 边的权值 Node *next; //下一条边的指针 }; struct HeadNode{ // 定义头结点 int nodeName; // 顶点信息

  • C++求所有顶点之间的最短路径（用Dijkstra算法）

    本文实例为大家分享了C++求所有顶点之间最短路径的具体代码,供大家参考,具体内容如下 一.思路: 不能出现负权值的边 (1)轮流以每一个顶点为源点,重复执行Dijkstra算法n次,就可以求得每一对顶点之间的最短路径及最短路径长度,总的执行时间为O(n的3次方) (2)另一种方法:用Floyd算法,总的执行时间为O(n的3次方)(另一文章会写) 二.实现程序: 1.Graph.h:有向图 #ifndef Graph_h #define Graph_h #include <iostream> u

  • C++实现Dijkstra(迪杰斯特拉)算法

    Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,是广度优先算法的一种,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离.当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性.不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破

  • 详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    目录 简介 工作过程 总体思路 实现 小根堆 Dijsktra 测试 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过

  • Java 迪杰斯特拉算法实现查找最短距离的实现

    迪杰斯特拉算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.具体的计算规则我们可以通过下图进行查看. 通过这幅图我们可以简单的理解迪杰斯特拉算法算法的基础思路,下面我们就通过JAVA来实现这个算法. 算法实现 在迪杰斯特拉算法中我们需要保存从起点开始到每一个节点最短步长,这也是图中需要比较得出的步长,同时我们还

  • js图数据结构处理 迪杰斯特拉算法代码实例

    js图数据结构处理 迪杰斯特拉算法代码实例

    这篇文章主要介绍了js图数据结构处理 迪杰斯特拉算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /*//1.确定数据结构, mapf[i][j] 为点i到点j的距离 [ Infinity 2 5 Infinity Infinity Infinity Infinity 2 6 Infinity Infinity Infinity Infinity 7 1 Infinity Infinity 2 Infinity 4 Infinity

  • Python实现迪杰斯特拉算法过程解析

    一. 迪杰斯特拉算法思想 Dijkstra算法主要针对的是有向图的单元最短路径问题,且不能出现权值为负的情况!Dijkstra算法类似于贪心算法,其应用根本在于最短路径的最优子结构性质. 最短路径的最优子结构性质: 如果P(i,j)={Vi-Vk-Vs-Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径. 证明: 假设P(i,j)={Vi-Vk-Vs-Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)

  • Python实现迪杰斯特拉算法并生成最短路径的示例代码

    def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径,并返回该路径和代价 print("Start Dijstra Path--") path=[]#s-d的最短路径 n=len(network)#邻接矩阵维度,即节点个数 fmax=999 w=[[0 for i in range(n)]for j in range(n)]#邻接矩阵转化成维度矩阵,即0→max book=[0 for i in range(n)]#是否已经是最小的标记列表 dis=[

  • java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题

    java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题

    目录 弗洛伊德算法 算法介绍 算法图解分析   迪杰斯特拉算法 算法介绍 算法过程  弗洛伊德算法 算法介绍 算法图解分析     第一轮循环中,以A(下标为:0)作为中间顶点 [即把作为中间顶点的所有情况都进行遍历,就会得到更新距离表和前驱关系],距离表和前驱关系更新为: 弗洛伊德算法和迪杰斯特拉算法的最大区别是: 弗洛伊德算法是从各个顶点出发,求最短路径: 迪杰斯特拉算法是从某个顶点开始,求最短路径. /** * 弗洛伊德算法 * 容易理解,容易实现 */ public void floyd

  • C/C++最短路径算法之迪杰斯特拉Dijkstra的实现详解

    C/C++最短路径算法之迪杰斯特拉Dijkstra的实现详解

    目录 前言 一.迪杰斯特拉(Dijkstra)算法是什么 二.实现步骤 1.算法思路 2.进入主函数ShortestPath() 1.创建final数组并且初始化path[].dist[]数组 2.对于节点的初始化 3.进入主循环 三.全部代码(邻接表下) 四.全部代码(邻接矩阵下) 五.测试代码(邻接表下) 总结 前言 我们在生活中常常面临对路径选择的决策问题,这就要用到最短路径的算法了. 对于我这种榆木脑袋,显然迪杰斯特拉的这种算法有点高深.主要是我笨. 对于网图来说,最短路径,就是指两个顶

  • 基于Python实现迪杰斯特拉和弗洛伊德算法

    图搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法,供大家参考,具体内容如下 Djstela算法 #encoding=UTF-8 MAX=9 ''' Created on 2016年9月28日 @author: sx ''' b=999 G=[[0,1,5,b,b,b,b,b,b],\ [1,0,3,7,5,b,b,b,b],\ [5,3,0,b,1,7,b,b,b],\ [b,7,b,0,2,b,3,b,b],\ [b,5,1,2,0,3,6,9,b],\ [b,b,7,b,3,0,b,5

随机推荐