迪杰斯特拉算法演示

⑴ 实现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算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过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)(网络)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
里面有个动图，更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)

⑶ 迪杰斯特拉算法的介绍

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

⑷ Dijkstra 算法是什么 Dijkstra 在哪里用

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径,该算法按照最短路径长度递增的顺序产生所以最短路径.
对于图G=（V,E）,将图中的顶点分成两组：
第一组S：已求出的最短路径的终点集合（开始为{v0}）.
第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）.
算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中,直到所有顶点都被加入到第一组顶点集S为止.
【算法思想】
g为用邻接矩阵表示的带权图.
（1）S

⑸ 迪杰斯特拉算法

按路径长度递增次序产生最短路径算法： 把V分成两组： （8）S：已求出最短路径的顶点的集合 （8）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证

⑹ 迪杰斯特拉算法的算法实现

· 算法思想
设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj ，则Vj只有：
◆ 源点到终点有直接的弧<Vs，Vj>；
◆ 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。
若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条最短路径。
· 示例程序
· 算法思想
var a:array[1..100,1..100]of integer;//邻接矩阵
flag:array[1..100] of boolean;//已经找到最短路径的节点标志
path:array[1..100]of integer;
w,x,n,i,j,min,minn,k:integer;
begin
readln(n,k);for i:=1 to n do//读取邻接矩阵,无路径写-1
begin
for j:=1 to n do
begin
read(a[i,j]);
If a[i,j]=-1 then a[I,j]:=maxint;
end;
readln;
end;
fillchar(flag,sizeof(flag),false);//标明所有节点都未找到最短路径
flag[k]:=true; //源节点除外
fillword(path,sizeof(path) div 2,k);
path[k]:=0;
minn:=k;//标记最小的点for x:=2 to n do
begin
min:=32767;//标记要找下一个最短路径点的距离
for i:=1 to n do//找下一点点
if (a[k,i]<min) and (flag[i]=false) then
begin
min:=a[k,i];
minn:=i;
end;
flag[minn]:=true;//标记下一个点的找到
for j:=1 to n do //更新最短路径
if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then
begin
a[k,j]:=a[k,minn]+a[minn,j];
path[j]:=minn;
end;
end;
for i:=1 to n do write(a[k,i],' ');//输出源点到各个点的距离
writeln;
for i:=1 to n do write(path[i],' ');//输出源点到各个点的距离
end.
求采纳（空格被网络吃了……）

⑺ dijkstra算法有哪些

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

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

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

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

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

(7)迪杰斯特拉算法演示扩展阅读：

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

⑻ Dijkstra 算法是什么

是求单源最短路算法,图中有一个起始点,求所有点对于这个起始点的最短距离
在路由器的协议里面有它的应用

还有问题可以继续hi我

⑼ 迪杰斯特拉算法怎么算

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。.

⑽ dijkstra算法是什么

迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。

算法把一个图（G）中的点划分成了若干部分：

1）：原点（v）；

2）：所有周边点（C）；

另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。

这样就可以进一步划分图（G）：

1）：原点（v）；

2）：已求出v至其最短路径的周边点（S）；

3）：尚未求出v至其最短路径的周边点（Other=C-S）；

算法的主体思想：

A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；

B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；

C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。

重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——