dijkstra算法做题

A. 用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，并写出执行算法过程中各步的状态。

迪克斯加（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到任何其他顶点的最短路径
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到u的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候每条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找权值最小的点为node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各点的权值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.

B. 解释一下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就和你的这本书中获得永久标号是相似的)

C. 离散数学迪克斯特拉算法解题详细过程

18·解：题中E、F分别在AA1、C1B1上，所以“展开”后的图形中必须有AA1、C1B1；故“展开”方式有以下四种：
（ⅰ）沿CC1将面ACC1A1和面BCC1B1展开至同一平面，如图1，求得：EF2=；
（ⅱ）沿BB1将面ABB1A1和面BCC1B1展开至同一平面，如图2，求得：EF2=；
（ⅲ）沿A1B1将面ABB1A1和面A1B1C1展开至同一平面，如图3，求得：EF2=；
（ⅳ）沿A1C1将面ACC1A1和面A1C1B1展开至同一平面，如图4，求得：EF2=；
比较可得（ⅳ）情况下，EF的值最小；
故EF的最小值为．

D. 利用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）。

以上内容参考：网络-最短路径算法

E. dijkstra算法是什么

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

对于图G=（V，E），将图中的顶点分成两组：第一组S：已求出的最短路径的终点集合（开始为｛v0}）。第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。

堆优化

思考

该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。

实现

1、将源点加入堆，并调整堆。

2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。

3、处理与u相邻的，未被访问过的，满足三角不等式的顶点

1):若该点在堆里，更新距离，并调整该元素在堆中的位置。

2):若该点不在堆里，加入堆，更新堆。

4、若取到的u为终点，结束算法；否则重复步骤2、3。

F. 利用Dijkstra算法,求下图从1出发到其余各点的最短路径.

MVC方法常用于构建用户界面在Smalltalk。通过MVC设计模式隐藏在可以帮助你了解我们所说的“模范”的意思。

MVC包括三种类型的对象，模型是应用程序对象，查看其屏幕表示，控制器定义了处理用户输入（响应）模式。在MVC方式之前，应用程序，通常是三个对象组合在一起，这些功能结合在一起，将它们分开MVC应用程序，旨在提供灵活性和可重用性。

MVC通过创建订阅/通知视图和模型，视图和模型对象之间的分离协议。视图对象必须确保它反映了状态模型表示对象，当数据模型对象的变化，模型对象的通知（通知）视图对象，作为反应，这种行为，每有一个视图对象进行更新的机会。这种方法使得有可能对多个视图的对象模型中的对象提供不同的表示形式。您还可以创建一个新的视图对象模型对象，而不是重新写模式。下图显示了一个模型和三视图：点击看详细从表面上看，这个例子反映的视图和模型设计的分离。然而，这是专为一类的更一般的问题：降低了莲和性的目的，这样，当一个对象改变时，也不会影响到其它的目的，甚至不需要知道另一个对象的实现细节。这更普遍的模式将在Observer模式描述。另一个特点是方式

MVC，视图对象是可嵌套定义。例如，通过嵌套对象视图对象按钮控制面板按钮视图包含复杂的实施;对象观众嵌套的用户界面视图的对象可以被重新使用的调试器组件。使用CompositeView类（查看子类），以支持嵌套图，其行为和查看对象，可用于任何场合视图对象可以使用的行为一致MVC方法。

因此，我们可以把复合视图这样的一种方式来解决它的设计（时尚）的一个组成部分。同样，这样的设计可以抽象另一个更普遍的问题（解决方案）：在某些情况下，我们进入的对象群体，并视为一组处理单个对象。通过这种方式，我们用它来形容复合设计模式。它可以让你建立一流的水平，在这个水平上，某些子类定义基本对象（如按钮），而其他类可以定义合成对象（CompositeView），合成对象可以组装成更复杂的对象原始对象。

同样，MVC也可以改变视图类（视图）的方式，用户的反应，不改变其视觉表现。你可能想改变其响应于键盘，如使用弹出菜单，而不是命令键的方式。 MVC封装的响应机制，该对象（控制器）的控制。控制器具有一个类层次结构，并且容易从现有的控制器来实现建立一个变种 - 一个新的控制器。

视图（View），通过对象（实例）控制器对象的实例，以实现特定的应对策略。为了实现不同的政策，可以简单地使用不同的控制器实例来替换当前实例。即使在运行时改变控制器的视图来改变响应于用户输入（策略）的对象图。例如，一个浏览对象可以被设置为关闭状态，即，在没有任何用户输入的响应。为了实现这一目标，就干脆让控制器忽略所有输入事件。这

视图 - 控制器关系，这是策略设计模式的一个典型例子。所谓策略，这样一种对象，它表示的算法。当你要替换算法（无论是静态还是动态替换替换），这是特别有用，这样的算法可能有很多变数，或有复杂的数据结构。

MVC中也使用其他的设计模式，例如，使用工厂方法模式来描述默认控制器类图;使用装饰图案添加滚动条，以查看等。但在MVC的方式主要是上述观察，综合和战略设计模式。

G. 用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

H. 提供几道Dijkstra算法的ACM水题练习

浙江大学ZOJ上的1221题可以算是最最基础的Dijkstra算法练习。。

由于Dijkstra 与 prim 有惊人的相似之处，所以这道题要好好体会。。

希望对你有所帮助！！！！！

本人相当建议初学者做做。。下面是本人的AC代码：

#include<iostream>
#include<algorithm>
using namespace std;

int map[21][21];
int flag[21];
int length[21];
int dijkstra(int from,int to)
//Dijkstra算法真的跟Prim很像。。要好好体会体会。。
{
int q,w,m;
memset(flag,0,sizeof(flag));
memset(length,0,sizeof(length));
for(q=1;q<=20;q++)
length[q]=map[from][q];
flag[from]=1;
length[from]=0;
for(q=1;q<20;q++)
{
int min=9999,y;
for(w=1;w<=20;w++)
{
if(flag[w]==0&&min>=length[w])

min=length[w],y=w;
}
flag[y]=1;
for(w=1;w<=20;w++)
{
if(flag[w]==0&&map[y][w]==1&&length[w]>length[y]+1)

length[w]=length[y]+1;
}
}
return length[to];
}
int main()

//这是比较简单的求无向图无权任意两点的最短距离
{
int t,q,w,m,count=1;
while(scanf("%d",&t)!=EOF)
//一开始这里我写为：while(1)。。本来是想让他不停输入的。。谁知道TLE了。。
{
for(q=1;q<=20;q++)
for(w=1;w<=20;w++)

map[q][w]=1000;
while(t--)
{
scanf("%d",&w);
map[1][w]=map[w][1]=1;
}
for(q=2;q<20;q++)
{
scanf("%d",&t);
while(t--)
{

scanf("%d",&w);

map[q][w]=map[w][q]=1;
}
}
scanf("%d",&w);
//cout<<"Test Set #"<<count<<endl;
printf("Test Set #%d\
",count);
count++;
int from,to;
while(w--)
{

scanf("%d %d",&from,&to);
//cout<<from<<" to "<<to<<":"<<dijkstra(from,to)<<endl;
printf("%d to %d: %d\
",from,to,dijkstra(from,to));
}
printf("\
");
}
return 0;
}

I. Dijkstra算法问题

dijkstra算法的时间复杂度是O(n²),
不妨设为kn²,其中次数小于1的项忽略
k(10×10）=10ms
那么k(40×40）=16[k×（10×10）]=160ms