dijkstra算法是什么

本文目录

• dijkstra算法是什么
• 利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式
• 算法手记Dijkstra双栈算术表达式求值算法
• 实现Dijkstra算法，并用图形化的方式显示出该算法的运算过程
• 用dijkstra算法计算源点到个结点的最短路径.谢谢亲爱的朋友~ 详细答案
• Dijkstra算法流程图
• dijkstra算法
• dijkstra算法有哪些
• 解释一下dijkstra算法这个计算过程的意思 怎么算的
• 关于Dijkstra算法

dijkstra算法是什么

Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。

不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。

Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。（u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E→[0,∞］定义。

因此，w(u,v)就是从顶点u到顶点v的非负花费值（cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。

已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径（i.e.最短路径）。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式

v1到v2：10为最短路径；

v1到v3：7为最短路径；

v1到v4：8为最短路径；

v1到v5：v1-》 v2 -》 v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=》O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

以上内容参考：百度百科-最短路径算法

算法手记Dijkstra双栈算术表达式求值算法

　　这两天看到的内容是关于栈和队列，在栈的模块发现了Dijkstra双栈算术表达式求值算法，可以用来实现计算器类型的app。
　　编程语言系统一般都内置了对算术表达式的处理，但是他们是如何在内部实现的呢？为了了解这个过程，我们可以自行搭建一套简易的算术表达式处理机制，这里就用到栈特性和本篇提到的Dijkstra算法。
　　概述：
　　算术表达式可能是一个数、或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。为了简化问题，这里定义的是未省略括号的算术表达式，它明确地说明了所有运算符的操作数，形式如下：
　　（1+（（2+3）*（4*5）））
　　思路：
　　表达式由括号、运算符和操作数构成，我们根据以下4中情况从左至右逐个将这些实体送入栈处理：
　　1.将操作数压入操作数栈；
　　2.将运算符压入运算符栈；
　　3.忽略左括号；
　　4.在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算后的结果压入操作数栈；
　　在处理完最后一个右括号时，操作数栈上只会剩下一个值，它就是表达式的计算结果。这种方法咋一看难理解，但要证明它能计算得到正确的值很简单：
　　每当算法遇到一个括号包围，并由一个运算符和两个操作数组成的子式时，他都将运算符和操作数运算结果压入操作数栈。这样的结果就像是在输入中用这个值代替了该子表达式，因此用这个值代替子表达式得到的结果和原表达式相同。我们可以反复应用这个规律并得到一个最终值。
　　例如：
　　（1+（（2+3）*（4*5）））
　　（1+（5*（4*5）））
　　（1+（5*20））
　　（1+100）
　　101
　　代码实现：
　　这里我采用C#来实现，最终运行效果完全符合预期，证明了此算法的正确性，代码如下：
　　using System;
　　using System.Collections.Generic;
　　using System.Linq;
　　namespace Evaluate
　　{
　　class Program
　　{
　　static void Main(string args)
　　{
　　string testExpress = “(1+((2+3)*(4*5)))“;
　　Console.WriteLine(Evaluate(testExpress));
　　}
　　//DijkStra
　　static double Evaluate(string express)
　　{
　　var expressChars = express.ToArray《char》();
　　Stack《char》 ops = new Stack《char》();
　　Stack《double》 vals = new Stack《double》();
　　if (express.Length 》 0)
　　{
　　foreach (var opt in expressChars)
　　{
　　switch (opt)
　　{
　　case ’+’:
　　case ’-’:
　　case ’*’:
　　case ’/’:
　　ops.Push(opt);
　　break;
　　case ’)’:
　　var op = ops.Pop();
　　var v = vals.Pop();
　　switch (op)
　　{
　　case ’+’:
　　v += vals.Pop();
　　break;
　　case ’-’:
　　v = vals.Pop() - v;
　　break;
　　case ’*’:
　　v *= vals.Pop();
　　break;
　　case ’/’:
　　v = vals.Pop() / v;
　　break;
　　}
　　vals.Push(v);
　　break;
　　case ’ ’:
　　case ’(’:
　　break;
　　default:
　　vals.Push(double.Parse(opt.ToString()));
　　break;
　　}
　　}
　　return vals.Pop();
　　}
　　return double.MaxValue;
　　}
　　}
　　}
　　总结：
　　Dijkstra算法充分利用了栈的特性，具备较高的执行效率，经过进一步的扩充修改，就完全可以实现具备科学计算功能的复杂计算类app。如果大家还有更好的，更适用的算法，欢迎在评论中给出地址，谢谢。
转载

实现Dijkstra算法，并用图形化的方式显示出该算法的运算过程

一般数据结构书上都会有
const int NumVertices=10 //假定最大10个顶点
class Gragh 图类定义（邻接矩阵表示）
{
private:
float Edge[NumVertices][NumVertices];
//邻接矩阵表示
float dist[NumVertices];
//顶点0到其他个顶点最短路径长度
int path[NumVertices];
//最短路径上该顶点的前一个顶点号,
int S[Numvertices];
/*已求得最短路径上顶点的顶点号，=1表示已经得 最短路径=0表示为未求得最短路径*/
public:
void Shortestpath(int ,int );//Dijkstra算法
int choose(int);
};
void Graph::Shortestpath(int n,int v)
{ //n是图的顶点数，v为所要求的顶点
for(int i=0,i《n;i++)
{//dist，path，S数组初始化
dist[i]=Edge[v][i];
S[i]=0;
if(i!=v&&dist[i]《MAXNUM)path[i]=v;
else path[i]=-1;
}
S[v]=1;dist[v]=0//v是起始顶点
for(i=0;i《n-1;i++)
{//从v确定n-1条路径
float min=MAXNUM;
int u=v;
for(int j=0;j《n;j++)
{//选择不在S中有最短路径的顶点u
if(!S[j]&&dist[j]《min)
{
u=j;min=dist[j];
}
S[u]=1;//顶点u加入S集合中
for(int w=0;w《n;w++)
if(!S[w]&&Edge[u][w]《MAXNUM&&
dist[u]+Edge[u][w]《dist[w])
{/*修改不在S中的其他顶点的当前最短路径*/
dist[w]=dist[u]+Edge[u][w];
path[w]=u;
}
}
}

用dijkstra算法计算源点到个结点的最短路径.谢谢亲爱的朋友~ 详细答案

(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa-》b表示a-》b的边的权值，d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1-》i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3． 对全部i属于S,如果存在边j-》i，那么置d(i)=min{d(i), d(j)+Wj-》i}，转2

Dijkstra算法流程图

定义G=(V,E)，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S
Dijkstra算法描述如下：
(1) 假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧《Vi, Vj》上的权值。若《Vi, Vj》不存在则置edges[i][j]=∞（计算机上用一个允许的最大值代替）。S为已经找到的从Vs出发的最短路径的终点集合，它初始化为空集。那么，从Vs出发到图上其余各顶点（终点）Vi可能达到的最短路径长度的初值为：D[i]=deges[s][i] Vi∈V
(2) 选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}
(3) 修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]《D[k]则修改D[k]为D[k]=D[j]+edges[j][k]
重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。

dijkstra算法

[问题分析]
对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想。
设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。
下面给出具体的Dijkstra算法框架（注：为了实现上的方便，用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。
Procedure Dijkstra(GA,dist,path,i)；
{表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，
其中path的基类型为集合}
Begin
For j:=1 To n Do Begin {初始化}
If j《》i Then s[j]:=0 Else s[j]:=1；
dist[j]:=GA[i,j]；
If dist[j]《maxint Then path[j]:=[i]+[j] Else path[j]:=[ ]；
End；
For k:=1 To n-2 Do
Begin
w:=maxint；m:=i；
For j:=1 To n Do {求出第k个终点Vm}
If (s[j]=0) and (dist[j]《w) Then Begin m:=j；w:=dist[j]； End；
If m《》i Then s[m]:=1 else exit；
{若条件成立，则把Vm加入到S中，
否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去}
For j:=1 To n Do {对s[j]=0的更优元素作必要修改}
If (s[j]=0) and (dist[m]+GA[m,j]《dist[j])
Then Begin Dist[j]:=dist[m]+GA[m,j]；path[j]:=path[m]+[j]；End；
End；
End；
（1）从一个顶点到其余各顶点的最短路径
对于一个含有n个顶点和e条边的图来说，从某个顶点vi到其余任一顶点vj的最短路径，可能是它们之间的边（vi，vj），也可能是经过k个中间点和k+1条边所形成的路径（1≤k ≤n-2）。
首先来分析Dijkstra的算法思想
设图G用邻接矩阵的方式存储在GA中，GA[I，j]=maxint表示vi，vj是不关联的，否则为权值（大于0的实数）。设集合S用来存储保存已求得最短路径的终点序号，初始时S=[vi]表示只有源点，以后每求出一个终点vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时vi，vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时vi到vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点vi到终点vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把vm并入集合S中，然后以vm作为新考虑的中间顶点，对S以外的每个顶点vj，比较dist[m]+GA[i，j]与dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把vj或边（vm，vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余个终点的最短路径长度，对应的path数组中保存着相应的最短路径。
为了实现上的方便，用一个一维数组s[1..n]代替集合s，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点vj不在集合中，反之，s[j]表示顶点vj已在集合中）。
Procedure dijkstra (GA,dist path,I)
begin
for j:= 1 to n do begin
if j《》I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}；
dist[j]:=GA[I,J];
IF dist [j]《maxint {maxint为假设的一个足够大的数}
Then path [j]:=[I]+[j]
Else path[j]:=[ ];
End;
For k:= 1 to n-1 do begin w:=maxint;m:=I;
For j:= 1 to n do{求出第k个终点Vm}
if (s[j]=0)and(dist[j]《w) then begin m:=j;w:=dist[j];end;
If m《》I then s[m]:=1 else exit;{若条件成立，则把Vm加入到s中，否则退出循环，因为
剩余的终点，其最短路径长度均为maxint，无需再计算下去}
for j:=1 to n do {对s[j]=0的更优元素作必要修改}
if (s[j]=0)and (dist[m]+GA[m,j]《dist[j])
then begin
dist[j]:=dist[m]+GA[m,j];
path[j]:=path[m]+[j];
End;
End;
End;
用集合的思想：
for k:=1 to n-1 do
begin
wm:=max;j:=0;
for i:=1 to n do
if not(i in s)and(dist[i]《wm) then begin j:=i;wm:=dist[i];end;
s:=s+[j];
for i:=1 to n do
if not(i in s)and(dist[j]+cost[j,i]《dist[i]) then
begin dist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+char(48+i);end;
end;

dijkstra算法有哪些

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。

对于图G=（V，E），将图中的顶点分成两组：

第一组S：已求出的最短路径的终点集合（开始为{v0}）。

第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。

算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中，直到所有顶点都被加入到第一组顶点集S为止。

扩展资料：

从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

参考资料来源：百度百科-Dijkstra算法

解释一下dijkstra算法这个计算过程的意思 怎么算的

　　最近也看到这个算法，不过主要是通过C语言介绍的，不太一样，但基本思想差不多。下面只是我个人的看法不一定准确。
　　Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。
　　基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。
　　
　　t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例5.3上面的步骤(2)(3)并不能体现
　　
　　t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j《L_j=+无穷。
　　这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。
　　
　　t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例5.3上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，
　　对于v_2, L_1+w_12=1+2=3《L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1);
　　对于v_3, L_1+w_13=1+7=8《L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1);
　　对于v_4, L_1+w_14=1+5=6《L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1);
　　v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小
　　
　　t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4《L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2); 其他不变。步骤(3), L_4=4最小。
　　
　　t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小
　　t=6: 同理
　　
　　啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。
　　
　　迪杰斯特拉算法(Dijkstra)(百度百科)：
(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)

关于Dijkstra算法

楼上正解，你找个图自己用此算法实践一下就知道了，从A点出发，发现离A最近的点是B点，那么我们就已经认为A到B的最短距离就是AB了，如果有负数，就指不定冒出个C点,AC+CB《AB;或者冒出个DE为很大的负值，AC+CD+DE+EF+FB《AB;等等诸如此类的情况。
简单说来，你驾车从家出发到某地沿某条路只需经过一个收费站，但是远在外省某地有个站不但不收你的费，你去了还会给你个千八百万的欢迎光临费，你能说你直接沿着这条路去某地是最省费用的？不计时间成本，绕到外省那个给你钱的地方，再绕回到你的目的地，还能赚钱呢。
而且一般权值为负的图研究也比较少。有些带负权的图，某些点间还没有最小距离呢。中间出个带某条负权很大的边的环圈，绕此一圈所经过的距离反而减少了，那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止。
当然考虑各种自己随便假设出来的变种问题也是很有趣的。比如说边带有多个权值对应多次经过改变的消费，上面的问题有可能变成有解的。话说那个站会后悔，第二次经过它会收回100万，第三次经过收回250万，这样的话你只需要经过一次就够了，问题也是有解的。再比如说对于多权重图，从A点出发经过B点到达C点的最短路线，就不是简单的AB最短路线+BC最短路线了，说不定两者有重合边，第二次经过来个天价就傻眼了。其实这种图貌似应该可以转化成单权重图的，我直觉估计啊，刚随便想出这个问题，还没去思考这个问题的解^_^