精华内容
下载资源
问答
  • Dijkstra算法(迪杰斯特拉算法) 本文主要介绍Dijkstra算法(迪杰斯特拉算法)的思想没有源码实现,但写出了思路流程。当你了解这个算法思想后会很容易写出源码。Dijkstra算法(迪杰斯特拉算法)是比较常用的最短路径算法...

    Dijkstra算法(迪杰斯特拉算法)

    本文主要介绍Dijkstra算法(迪杰斯特拉算法)的思想没有源码实现,但写出了思路流程。当你了解这个算法思想后会很容易写出源码。Dijkstra算法(迪杰斯特拉算法)是比较常用的最短路径算法,可以算是贪心思想的实现。贪心思想是在对问题求解时,总是做出在当前看来是最好的选择。
    Dijkstra算法核心就是求出局部最优解。下面用open,close表描述Dijkstra算法的过程。
    首先介绍下open表和close表,open表用于存储未探索的节点,也可以理解为这次探索到的新节点。close表用于存储已经探索过的节点(当前最优路线)。
    在这里插入图片描述

    初始化将起点分别放入open表和close表中。open表是一个优先队列(用set实现元素结构为坐标和距离起点的长度)每次弹出最小值。close表是一个map(key为当前节点下标,value元素为结构为前一节点下标和距离起点长度)通过当前坐标寻找前指针和当前坐标距离起点的长度。循环步骤如下:1.2
    1.从open表中弹出距离起点最近的节点,判断下探索到的节点是否为终点(每次弹出的都是最优路线),探索该节点的相邻节点。
    这里说明下为什么open表弹出来的就是最优路线,弹出的节点到达起点的路径已经是最短路径,经过其他大于该节点的节点到达该节点,距离一定大于此次弹出的这个距离。
    2.探索到的相邻节点先到close表中去查找是否被探索过,如果被探索过就比较距离,如果此次距离小于close表中存储的距离那么就更新close表(更新前指针和距离)和open表(更新距离),此次距离不小于close表中存储的距离就可以忽略本次;如果close表中不存在该节点那么直接插入到close表中,并插入open表中。
    这里说明下为什么更新open表,因为close表中出现了该节点被探索过所以open表中一定存在距离起点长度大于此次探索到的节点距离起点的长度,open每次是弹出距离起点最短的节点,如果不更新就会导致节点弹出顺序错误。
    初始化:
    open表:起点坐标为0,距离起点距离为0,此时该set中只有一个元素
    在这里插入图片描述
    close表:起点的坐标为0,距离起点距离为0
    在这里插入图片描述
    第一次循环:
    弹出open首节点(set自动排序最小值在最前面)
    找到相邻节点为1,2节点,到close表中查找1,2节点是否存在,不存在直接插入表close,同时插入open表
    第一次循环
    第二次循环:
    继续弹出open首节点1
    找到相邻节点2,3节点,到close表中查找2,3节点是否存在,2节点存在则比较距离
    (0->1->2=10)<(0->2=12)所以更新close中2节点,3节点不存在直接插入close,同时更新open表中2节点和插入3节点
    第二次循环第三次循环:
    继续弹出open首节点3
    找到相邻节点2,4,5节点,到close表中查找2,4,5节点是否存在,2节点存在则比较距离
    (0->1->3->2=8)<(0->1->2=10)所以更新close中3节点,4,5节点不存在直接插入close,同时更新open表中2节点和插入4,5节点
    第三次循环
    第四次循环:
    继续弹出open首节点2
    找到相邻节点4节点,到close表中查找4节点是否存在,4节点存在则比较距离
    (0->1->3->2->4=13)<(0->1->3->4=17)更新open和close
    第四次循环
    第五次循环:
    继续弹出open首节点4
    找到相邻节点5节点,到close表中查找5节点是否存在,5节点存在则比较距离
    (0->1->3->2->4->5=17)=(0->1->3->5=19)更新close更新open 第五次循环
    6.弹出顶点判断顶点为终点结束循环

    总结

    Dijkstra算法利用优先队列可以自己排序的优势每次弹出的都是当前最优路径和上一篇写过的广度优先算法对比优势一目了然。
    广度优先算法链接:https://blog.csdn.net/qq_33865609/article/details/117062138
    以上文章作者通过上网查找资料自己思考总结而来,如有不足,不吝赐教,谢谢。

    展开全文
  • 又去学了迪杰斯特拉算法 其实和最下生成树prim基本差不多 就是遍历做标记然后循环,把最短的记录下来,遇到更短的就换掉 还有拓扑用数组容量不够了100000*100000 改用用链表解决了 把二维数组换成 一个结构体数组...

    遇到floyd优化了也时间超限的题
    只会floyd很难受
    又去学了迪杰斯特拉算法
    其实和最下生成树prim基本差不多
    就是遍历做标记然后循环,把最短的记录下来,遇到更短的就换掉

    还有拓扑用数组容量不够了100000*100000
    改用用链表解决了
    把二维数组换成 一个结构体数组然后再用指针不断地指子项这样的

    展开全文
  • 迪杰斯特拉算法(解决单源最短路径) 基本思想:每次找到离源点(如1号节点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。 基本步骤:1,设置标记数组book[]:将所有的顶点...

    一、算法介绍

    迪杰斯特拉算法(解决单源最短路径)

    基本思想:每次找到离源点(如1号节点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。

    基本步骤:1,设置标记数组book[]:将所有的顶点分为两部分,已知最短路径的顶点集合P和未知最短路径的顶点集合Q,很显然最开始集合P只有源点一个顶点。book[i]为1表示在集合P中;

    2,设置最短路径数组dst[]并不断更新:初始状态下,dst[i]=edge[s][i](s为源点,edge为邻接矩阵),很显然此时dst[s]=0,book[s]=1.此时,在集合Q中可选择一个离源点s最近的顶点u加入到P中。并依据以u为新的中心点,对每一条边进行松弛操作(松弛是指由顶点s-->j的途中可以经过点u,并令dst[j]=min(dst[j],dst[u]+edge[u][j])),并令book[u]=1;

    3,在集合Q中再次选择一个离源点s最近的顶点v加入到P中。并依据v为新的中心点,对每一条边进行松弛操作(即dst[j]=min(dst[j],dst[v]+edge[v][j])),并令book[v]=1;

    二、示例代码

    #include <iostream>
    #include <vector>
    using namespace std;
    #define Max 100
    #define inf 99999
    struct Edge
    {
    	int cost,len;
    	int next; 
    };
    vector<Edge> edge[Max];
    int dst[Max],book[Max],m,n,stNode,enNode,spend[Max];
    int main(){
    	cin>>n>>m;
    	int a=0,b=0;
    	for(int i=1;i<m;i++)
    	{
    		cin>>a>>b;
    		Edge tmp;
    		cin>>tmp.len>>tmp.cost;
    		tmp.next=b;
    		edge[a].push_back(tmp);
    		Edge tmp2;
    		tmp2.len=tmp.len;
    		tmp2.cost=tmp.cost;
    		tmp2.next=a;
    		edge[b].push_back(tmp2);
    	}
    	cin>>stNode>>enNode;
    	for(int j=1;j<=n;j++)
    	{
    		dst[j]=inf;
    		spend[j]=0;
    	}
    	int sn=edge[stNode].size();
    	for(int j=0;j<sn;j++)
    	{
    		int index=edge[stNode][j].next;
    		dst[index]=edge[stNode][j].len;
    		spend[index]=edge[stNode][j].cost;
    	}
    	book[stNode]=1;
    	for(int i=1;i<n;i++)
    	{
    		int minNode,min=inf;
    		for(int j=1;j<=n;j++)
    		{
    			if(book[j]==0 && min>dst[j])
    			{
    				minNode=j;
    				min=dst[j];
    			}
    		}
    		book[minNode]=1;
    		int s=edge[minNode].size();
    		for(int j=0;j<s;j++)
    		{
    			int index=edge[minNode][j].next;
    			if(book[index]==0 && dst[index]>dst[minNode]+edge[minNode][j].len)
    			{
    				dst[index]=dst[minNode]+edge[minNode][j].len; 
    				spend[index]=spend[minNode]+edge[minNode][j].cost; 
    			}
    		}
    	}
    	cout<<dst[enNode]<<" "<<spend[enNode]<<endl;
    	return 0;
    }

     

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

    2019-09-29 10:53:43
    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业...

    定义

    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

    算法思想

    按路径长度递增次序产生最短路径算法:
    把V分成两组:
    (1)S:已求出最短路径的顶点的集合
    (2)V-S=T:尚未确定最短路径的顶点集合
    将T中顶点按最短路径递增的次序加入到S中,
    保证:(1)从源点V0到S中各顶点的最短路径长度都不大于
    从V0到T中任何顶点的最短路径长度
    (2)每个顶点对应一个距离值
    S中顶点:从V0到此顶点的最短路径长度
    T中顶点:从V0到此顶点的只包括S中顶点作中间
    顶点的最短路径长度
    依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的
    直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和
    (反证法可证)

    求最短路径步骤

    算法步骤如下:
    1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值
    若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值
    若不存在<V0,Vi>,d(V0,Vi)为∝
    2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S
    3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的
    距离值缩短,则修改此距离值
    重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止

    转载于:https://www.cnblogs.com/byfei/archive/2013/03/28/2987309.html

    展开全文
  • 用于求解路径规划算法,Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的...
  • dijkstra算法(迪杰斯特拉算法) 用途:有向图最短路径问题 定义:迪杰斯特拉算法是典型的算法,一般的表述通常有两种方式,这里均采用永久和临时标号的方式,该算法要求图中不存在负权边 用永久和临时标号方式...
  • 最短路径,我们这次介绍迪杰斯特拉算法 其实我一直有一个疑问?我介绍的最小生成树2种算法,还有这次的 迪杰斯特拉算法都是在矩阵的基础上记性操作的,我很想知道如果 顶点的个数很多,有10000个,那么如果开一个...
  • 文章目录前言一、邻接二、迪杰斯特拉算法三、从文件读入邻接四、获取中间结点到其他节点的距离五、将最短路径的正序放入path六、码代码过程中遇到的各种问题1.typedef 结构体 链表2.Malloc free,堆溢出3....
  • 与邻接矩阵表示的方法不同的是,在更新dis数组和path数组时,只需要把求u到j距离的g.edges[u][j]换成邻接表示 g.edges[u][j]表示u到j的距离,因此可以写一个getWeight(g, u, j)算法用于计算u到j的距离 [核心函数]...
  • (七)1.2_迪杰斯特拉算法求最短路径

    千次阅读 2019-01-23 16:24:24
    一:迪杰斯特拉算法   假如以顶点v1起点,用迪杰斯特拉算法求起点分别到顶点v2,v3,v4,v5的最短路初始我们计算出起点到各个顶点的最短路径,然后连接路径是所有路径中最短的那个顶点(加入到S集),然后接着重复这样的...
  • 5 9 ------------------------5是节点数,9是边数 1 2 1 1 3 3 1 4 5 1 5 8 2 3 1 2 5 5 3 4 1 3 5 2 4 5 4 1 ------------------------- 根节点 1 2 3 4 5 --------------- 输出该点到根节点的最短路径 ...
  • 迪杰斯特拉算法的本质,是不断刷新起点与其他各个顶点之间的 “距离”。 算法实现 mport java.util.*; import java.lang.Integer; public class Dijkstra { public static Map<Integer, Integer> dijkstra...
  • 迪杰斯特拉算法实现单源最短路 使用了 邻接来存放图的信息,使用了优先级队列。 #include <iostream> #include<queue> #include<vector> #include<cstdio> #include<cstring> #...
  • 储存结构,结构体的定义:...typedef struct ENode//图的邻接定义 { int adjVex;//任意顶点u相邻接的顶点 int w;//边的权值 struct ENode* nextArc;//指向下一个边结点 }ENode; typedef struct LGraph { ...
  • 迪杰斯特拉算法: 1.假设用带权的邻接矩阵arc,来表示带权有向图,arc[i][j],表示弧<vi,vj>上的权值。若<vi,vj>不存在,则置arc[i][j]为无穷。 S为已找到从v出发的最短路径的终点的集合,它的初始状态...
  • 该题用邻接矩阵存储数据会导致超出内存,因此需要用邻接存储数据。 数组模拟邻接: head[i]表示该条边是从i开始的第head[i]条边; edge结构体存储该条边的第二个结点to,权值w,下一条边next;

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 219
精华内容 87
关键字:

迪杰斯特拉算法表