用d算法求v1到其他各点的距离

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

2. 从某个源点到其余各顶点的最短路径

要代码?? 怎么还熟练使用C++可视环境.
代码就不发了,数据结构的书上写的很详细 改改就能用了.
DLL 函数 __declspec(dllexport) 加到函数前面就成导出的了,
可以用LordPE 查看导出表查看其他DLL的导出函数
调试方法 看看手册 F5调试执行,F7单步F8步过F9断点,其余自己摸索下
在工程调试里面可以设置Memory,Stack,Watch,Auto,自己观察下就会了

3. 数据结构求最短路径

用Dijkstra算法求从V1顶点到其他各顶点的最短距离和最短路径的C语言程序如下

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define N 6 // 顶点数

#define INF 32767

int adj_arr[N][N] = {{INF, 2, 3, INF, INF, INF},

{INF, INF, INF, 5, INF, INF},

{INF, INF, INF, 3, 10, INF},

{INF, INF, INF, INF, INF, 4},

{INF, INF, INF, INF, INF, INF},

{INF, INF, INF, INF, 2, INF}}; // 用一个全局二维数组存储带权有向图的邻接矩阵

void shortest_path(int start, int end);

void print_shortest_path(int* distance,int* path,int* used,int start,int end);

int main(){

int i;

char s1[3];

for(i=1;i<6;i++){

shortest_path(0, i);

}

return 0;

}

void shortest_path(int start, int end){ // 基于Dijkstra算法的最短路径函数

int distance[N]; // 用于存放起始点到其余各点的最短距离

int path[N]; // 用于存放起始点到其余各点最短路径的前一个顶点

int used[N] = { 0 }; // 用于标记该顶点是否已经找到最短路径

int i, j, min_node, min_dis, pass_flag = 0;

for(i = 0; i < N; i++){

distance[i] = adj_arr[start][i]; // 初始化距离数组

if(adj_arr[start][i] < INF){

path[i] = start; // 初始化路径数组

}else{

path[i] = -1;

}

}

used[start] = 1;

path[start] = start;

for(i = 0; i < N; i++){

min_dis = INF;

for(j = 0; j < N; j++){

if(used[j] == 0 && distance[j] < min_dis){

min_node = j;

min_dis = distance[j];

pass_flag++; // 标记是否存在通路

}

}

if(pass_flag != 0){

used[min_node] = 1;

for(j = 0; j < N; j++){

if(used[j] == 0){

if(adj_arr[min_node][j] < INF && distance[min_node] + adj_arr[min_node][j] < distance[j]){

distance[j] = distance[min_node] + adj_arr[min_node][j];

path[j] = min_node;

}

}

}

}else{

printf("没有通路! ");

return;

}

}

print_shortest_path(distance, path, used, start, end);

return;

}

void print_shortest_path(int* distance,int* path,int* used,int start,int end){ // 输出最短距离并打印最短路径

int i = 0, pre, inverse_path[N];

char s1[3],s2[3];

sprintf(s1, "V%d", (start+1));

sprintf(s2, "V%d", (end+1));

printf("从%s顶点到%s顶点的最短距离: %d ", s1, s2, distance[end]);

inverse_path[i] = end;

pre = path[end];

if(pre == -1){

printf("没有通路! ");

}else{

while(pre != start){

inverse_path[++i] = pre;

pre = path[pre];

}

inverse_path[++i] = start;

printf("从%s顶点到%s顶点的最短路径: ", s1, s2);

for(; i > 0; i--){

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s -> ", s1);

}

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s ", s1);

}

return;

}

4. 已经图G的边权矩阵D[1],D[2],D[3]、、、D[n]，已经Vi到Vj的最短距离是c，找出Vi到Vj的中间过程。

算法过程把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。
定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。 把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。
在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。 比如，要寻找从V5到V1的路径。
根据D，假如 D(5,1)=3，D(3,1)=2，D(2,1)=1则说明从V5到V1经过V3，从V3到V1经过V2，V2到V1直接相连，路径为 {V5,V3,V2,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连

5. 迪杰克斯拉算法怎么也不明白

当然不一样啦，迪杰克斯拉算法，求的是单点到其他顶点最短的路径长度，而PRIM算法求的最小代价生成树

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

7. 求程序 在matlab上用Dijkstra和Floyd算法求出v1到v8的最短路径。。

function[distance,path]=Dijkstra(W,st,e)
n=length(W);
D=W(st,:);
visit=ones(1:n);
visit(st)=0;
parent=zeros(1,n);
path=[];

fori=1:n-1
temp=[];
forj=1:n
ifvisit(j)
temp=[tempD(j)];
else
temp=[tempinf];
end
end
[~,index]=min(temp);
visit(index)=0;

fork=1:n
ifD(k)>D(index)+W(index,k)
D(k)=D(index)+W(index,k);
parent(k)=index;
end
end
end

distance=D(e);
t=e;
whilet~=st&&t>0
path=[t,path];
p=parent(t);t=p;
end
path=[st,path];%最短路径
end

W=[0310InfInfInfInfInf;
30Inf5InfInfInfInf;
10Inf06InfInfInfInf;
Inf5604InfInfInf;
InfInfInf4095Inf;
InfInfInfInf9034;
InfInfInf105306;
InfInfInfInfInf460];
[distance,path]=Dijkstra(W,1,8);


>>distance
distance=
23
>>path
path=
124578

8. 已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路

初始化d[i]为无穷大，由于从v4开始，所以将d4=0，标记v4已选择。
下面开始Dijkstra算法：
和v4相连的且未标记的点有v2和v6，这样更新d2=20，d6=15，选择未标记所有点中最小的d6=15，标记v6已选择，这样我们算出了v4->v6最短距离d6=15；
从v6开始，和v6相连的且未标记的是v2，此时算d6+6=21>20,所以不更新d2，选择未标记所有点中最小的d2=20，标记v2已选择，这样算出了v4->v2最短距离d2=20；
从v2开始，和v2相连的且未标记的有v1和v5，d1=d2+10=30,d5=d2+30=50，选择未标记所有点中最小的d1=30，标记v1已选择，这样我们算出了v4->v1最短距离d1=30；
从v1开始，和v1相连的且未标记的有v3，d3=d1+15=45，选择剩下没被选的所有点的最小的d3=45(d5=50)，标记v3已选择，这样我们算出了v4->v3最短距离d3=45
从v3开始，没有出去的路径，不更新距离，选择剩下没被选的所有点的最小的d5=50，标记v5已选择，这样我们算出了v4->v5最短距离d5=50.
此时所有的点都被访问，结束。
注：上面的标记点已选择注意下，在算法的实现中用的是将所有的点放入队列中，一旦一个点被选择就是说求出了最短距离，就从此队列删除该点，一直到此队列为空，结束算法，我写标记只是为了方便理解。
希望能帮你清晰了解Dijkstra算法，图论中很重要的算法之一。

9. 试用Dijkstra算法求从v1到其余各顶点的最短路径，写出每一步的状态。求大神解答。算法我会，主