关于dijkstra算法的一点理解

关键词：

　　最近在准备ccf，各种补算法，图的算法基本差不多看了一遍。今天看的是Dijkstra算法，这个算法有点难理解，如果不深入想的话想要搞明白还是不容易的。弄了一个晚自习，先看书大致明白了原理，就根据书上的代码敲，边敲边深入思考，第一遍敲完运行失败，然后回过头在分析代码，改进还是失败。经过三次修改总算勉强跑起来了，但是结果还是不对，找了半天也找不出来。感觉整个人都不好了，弄了快三个小时结果还是有问题。时间差不多就回宿舍，在路上边走边想终于找到自己代码的问题了，回到宿舍代码修改后终于完美运行。经过一晚上的不断思考深入，反复推敲，得到了完美结果，付出和回报是成正比的。

　　好了！大致讲一下自己对这个算法的理解吧！首先要想弄明白这个算法还是得了解一下广度优先搜索的原理，这个算法就是基于广搜的原理得出来的一个算法。算法的核心又有点贪心算法的味道，所以说这个算法相当经典。Dijkstra算法是求单个节点到图中其他所有节点的最短距离，为了解决这个问题，首先要引入三个数组D[i](记录起始点到其他各点的最短距离),mark[i](表示每个节点的是否已经访问过),p[i](记录每个节点的前驱结点，便于观察最后到各个顶点的路径)。

　　Dijkstra算法的执行步骤:1.先初始化D[i]=v与i之间的距离(若两点不相连则为INIFY),mark[i]=0,p[i]=0,并将起始节点v的mark[v]=0;

　　　　　　　　　　　　　 2.遍历剩余的节点，找出剩余节点与v之间的距离(初始状态下除去相连的节点间有距离外其余所有节点间距离为INIFY)，不相连的节点依然设为INIFY不变。找出其中与v距离最小的那个点k，mark[k]=1;

　　　　　　　　　　　　   3.遍历所有节点，对其中mark[i]==0的点与k点的距离+2中的那个最小距离与D[i]比较，若小于D[i]则更新D[i]，并将p[i]标记为k(k为该节点的前驱)。

　　　　　　　　　　　　　4.遍历完后得到的D[i]就是v到各个节点的最短距离.

#include<iostream>

using namespace std;
#define INFTY 10000

class Graph
{
public:
    Graph(int n);        //构造函数初始化 
    ~Graph();            //析构函数销毁 
    void SetEdge(int v1,int v2,int weight);        //设置图中的相连边及其权值
    void Dijkstra(int v0);        //迪杰斯特拉算法 
    void Print(); 
private:
    int numVex;            //顶点数 
    int numEdge;        //边数 
    int **matrix;        //图
    int *mark;            //顶点标记 
    int *p;                //表示PathMatrix最短路径的前驱结点 
    int *D;                //表示ShortPathTa即两点间的带权长度 
};

Graph::Graph(int n)
{
    numVex=n;
    numEdge=0;
    mark=new int[numVex];
    p=new int[numVex];
    D=new int[numVex]; 
    matrix=new int*[numVex];
    for(int i=0;i<numVex;i++)
    {
        matrix[i]=new int[numVex];
    }
    for(int i=0;i<numVex;i++)
    {
        mark[i]=0;
        p[i]=0;
        D[i]=0;
    }
    for(int i=0;i<numVex;i++)
    {
        for(int j=0;j<numVex;j++)
        {
            matrix[i][j]=matrix[j][i]=INFTY;
        }
    }
} 

Graph::~Graph()
{
    delete []p;
    delete []D;
    delete []mark;
    for(int i=0;i<numVex;i++)
    {
        delete []matrix[i];
    }
    delete []matrix;
}

void Graph::SetEdge(int v1,int v2,int weight)
{
    matrix[v1][v2]=matrix[v2][v1]=weight;
}

void Graph::Dijkstra(int v0)
{
    int k,min;
    for(int i=0;i<numVex;i++)
    {
        D[i]=matrix[v0][i];
    }
    D[v0]=0;     
    mark[v0]=1;        //表示已经求得v0点的最短路径 
    for(int i=1;i<numVex;i++)
    {
        min=INFTY;
        for(int j=0;j<numVex;j++)
        {
            if(!mark[j] && D[j]<min)
            {
                k=j;
                min=D[j];
            }
        }
        mark[k]=1;    //表示从v0到k已经找到最短路径 

        //修正目前的最短路径 
        for(int j=0;j<numVex;j++)
        {
            if(!mark[j] && (min+matrix[k][j]<D[j]))
            {
                D[j]=min+matrix[k][j];    //修改当前路径的长度 
                p[j]=k;            //存放当前节点的前驱 
            }
        }
    }
}

void Graph::Print()
{
    cout<<"v0到各顶点的最短距离:"<<endl;
    for(int i=0;i<numVex;i++)
    {    
        cout<<D[i]<<" ";
    }
    cout<<endl;
    cout<<"各顶点的前驱顶点:"<<endl;
    for(int i=0;i<numVex;i++)
    {    
        cout<<p[i]<<" ";
    }
}

int main()
{
    int n,m,t;
    cout<<"请输入顶点数n和边数m"<<endl;
    cin>>n>>m;
    Graph G(n);
    int v1,v2,weight;
    cout<<"请输入顶点v1，v2及两顶点间边的权值"<<endl;
    for(int i=0;i<m;i++)
    {
        cin>>v1>>v2>>weight;
        G.SetEdge(v1,v2,weight);
    }
    cout<<"请输入迪杰斯特拉算法的起始顶点"<<endl;
    cin>>t; 
    G.Dijkstra(t);
    G.Print();
    
    return 0;
}

　　代码自己写的，可以完美运行！希望对大家有帮助。

关于我对vxlan的一点理解

关于我对VXLAN的一点理解我的一些朋友之前一直在谈论vxlan如何如何，今天我就自己对vxlan的一点理解，简单写写，希望对大家有所帮助。1、为什么要引入vxlan？1）在同一个数据中心我们一般通过VLAN对业务进行不同的网段划分，... 查看详情

关于maven的一点理解

maven是一个项目管理工具，主要作用是：1、依赖管理（jar包，工程之间）;2、统一开发规范和工具。完成项目的一步构建3、工程聚合、继承、依赖其核心配置文件就是pom.xml；pom即ProjectObjectModel 项目对象模型；用来描述整个Ma... 查看详情

关于c中数组和指针的一点理解

 今天在看了专家c的第四章后对数组和指针有了更深入的理解 首先1/*文件1*/2intp[100];34/*文件2*/5externint*p;67/*.........................*/89/*.............对p[i]相关的操作.................*/ 为什么会这样呢?指针和数组难道不就是一个... 查看详情

关于char*和char[]的一点理解

截取一段有用的信息： c++的char[]和char*的区别charstr1[]="abc"：   这里的"abc"是一个常量，首先会在常量存储区里存储"abc"这个常量，然后会因为"abc"被赋值给str1[]，所以在栈中开辟一段内存，内存大小为4个节点（char... 查看详情

关于js中变量提升的规则和原理的一点理解

上篇文章中讲到变量提升和函数提升的先后顺序时蒙了，后来去查了一下资料，特别整理一下。在《你不知道的JavaScript（上卷）》一书的第40页中写到：函数会首先被提升，然后才是变量。书中的一个代码示例是：foo();//1varfoo;fu... 查看详情

关于js中变量提升的规则和原理的一点理解

????关于变量提升，以前在一些教程和书籍上都听到过，平时开发中也知道有这个规律，但是今天突然在一个公开课中听到时，第一反应时一脸懵逼，然后一百度，瞬间觉得好熟悉啊，差点被这个概念给唬住了，不信我给你看个... 查看详情

关于正则方法的一点理解

正则表达式 1、元字符 元字符是正则表达式的基础，比如d--[0-9]数字字符，D--[^0-9]非数字字符；还有转义符f--换页， --换行；边界^--字符串起始位置,$--字符串结束位置，量词*--重复零次或更多x>=0，+--重复一次或更多次x... 查看详情

关于tensorflowconv2d卷积备忘的一点理解

**************input**************[[[[-0.36166722 0.04847232 1.20818889-0.1794038 -0.53244466]  [-0.67821187-1.81838071 0.59005165-1.17246294 0.33203208]  [ 查看详情

关于防抖和节流的一点理解

 今天刷面试题又双叒叕看到了防抖和节流，所以把自己的理解记录一下，欢迎指正。  防抖：在事件被触发n秒后再执行回调，如果在这n秒内又被触发，则重新计时。    我的理解就是打野怪的时候原本n... 查看详情

关于并发可见性的一点理解

 在看《深入理解计算机系统》（CSAPP）第6章存储器层次结构的时候突然想到在java并发编程中的可见性的问题，在这里简单记录一下，也不一定正确^_^我们从上面的图中可以看到IntelCorei7中有4核，每一个核心中都有独立的L1L2... 查看详情

自己关于es6的一点理解

首先要想声明‘usestrict‘!!!在定义常量的时候用const,定义变量的时候用let;当然可以所有都用const在报错的时候找出错误将错误改成let，不过如果是代码错误就没办法了在es6中个人感觉很友好的就是，不再具有变量提升的效果，免... 查看详情

scarletthln关于算法的一点总结

1.分解问题的角度:fix某一维度，尝试另一维度上的所有可能  a.可能是array的(i,j)pointers,b.可能是矩形的长与宽,c.可能是tree的每一个subtree,d.可能是情景题的每一对pair...2.求所有解的,暴力上backtracking吧3.如果问最短/最少的,先... 查看详情

关于dijkstra算法

Dijkstra算法1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算... 查看详情

算法描述》关于spfa和dijkstra算法的两三事

...来我是想把这两个算法分开写描述的，但是SPFA其实就是Dijkstra的稀疏图优化，所以其实代码差不多，所以就放在一起写了。　　因为SPFA是Dijkstra的优化，所以我想来讲讲Dijkstra。　　什么是Dijkstra　　Dijkstra是一种求单源最短路的... 查看详情

dijkstra算法-最短路径算法

2017-07-26 22:30:45writer：pprpdijkstra算法法则：设置顶点集合S，首先将起始点加入该集合，然后根据起始点到其他顶点的路径长度，选择路径长度最小的顶点加入到集合S，根据所加入顶点更新源点到其他顶点的路径长度，然后再... 查看详情

关于逆向360相关的一点感想

前两天，在忙一个东西，逆Win10设置默认浏览器的一个算法，这个算法是设置Win10操作系统最新版本的默认浏览器，所以肯定是微软自己的算法，360要么有源码，要么逆向出来的。因为，涉及到一些不该说的东西，所以我就不贴... 查看详情

(总结)关于dijkstra的一些看法

1）Dijkstra算法只能适用于权为正的图，有向图和无向图都可以用。2）Dijkstra算法在权为正的图中，如果图恰好是环，那Dijkstra算法也能用，还可以输出最短路。3）Dijkstra算法的本质是贪心，但是，这个可以求出最优解。它和Prim算... 查看详情

关于数据挖掘和数据分析的一点迷思！

关于数据分析和数据挖掘学习的一点迷思可能有些数据挖掘工程师的工作就是研究算法研究数学，不需要他们去做数据清洗，做报表展示类的工作，这类就是大牛了，不需要再读下去了关于数据这条路大家的一致认为业务和数学... 查看详情