急求dijkstra算法的程序

算法基本思想

　设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。

①初始化

　初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。

②重复以下工作，按路径长度递增次序产生各顶点最短路径

　在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。

　当蓝点集中仅剩下最短神改距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。

注意：

　①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。

　②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。

（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集

　根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：

　源点，红点1，红点2，…，红点n，蓝点k

距离为：源点到红点n最短距离+<红点n,蓝点k>边长

　为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈

V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。

　若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i]

i∈V-S}，则D[k]=SD(k)。

　初始时，每个蓝点v的D[c]值应为权w<s，v>，且从s到v的路径上没有中间点，因为该路径仅含一条边<s，v>。

注意：

　在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键

（4）k扩充红点集s后，蓝点集估计距离的修改

　将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。

　对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。

　所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。

（5）Dijkstra算法

Dijkstra(G，D，s){

//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度

//以下是初始化 *** 作

S={s}；D[s]=0；

//设置初始的桥瞎差红点集及最短距离

for(

all

i∈

V-S

)do

//对蓝点集中每个顶点i

D[i]=G[s][i]；

//设置i初始的估计距离为w<s，i>

//以下是扩充红点集

for(i=0i<n-1i++)do{//最多扩充n-1个蓝点到红点集

D[k]=min{D[i]：all

i

V-S}；

//在当前蓝点集中选估计距离最小的顶点k

if(D[k]等于∞)

return；

//蓝点集中所有蓝点的估计距离均为∞时，

//表示这些顶点的最短路径不存在。

S=S∪{k}；

//将蓝点k涂红后扩充到红点集

for(

all

j∈V-S

)do

//调整剩余蓝点的估计距离

if(D[j]>D[k]+G[k][j])

//新红点k使敏皮原D[j]值变小时，用新路径的长度修改D[j]，

//使j离s更近。

D[j]=D[k]+G[k][j]；

}

}

你对图论的知识有了解吧~W是关联矩阵，s和t分别是起始点和终止节点的序号。返回的d为最短的加权路拦升返径长度,p为最优路径节点的序号向量。注意，这里W矩阵为0的点权值已经自动设为无穷大了笑桐。请参考《高等应用数学问题的 MATLAB一书》。我吧程序赋给你。

你做一个M函数用吧。

function [d,path]=dijkstra(W,s,t)

[n,m]=size(W)ix=(W==0)W(ix)=inf

if n~=m,error('简饥Square W required')end

visited(1:n)=0dist(1:n)=infparent(1:n)=0dist(s)=0d=inf

for i=1:(n-1),%求出每个节点与起始点的关系

ix=(visited==0)vec(1:n)=infvec(ix)=dist(ix)

[a,u]=min(vec)visited(u)=1

for v=1:n,if (W(u,v)+dist(u)<dist(v)),

dist(v)=dist(u)+W(u,v)parent(v)=u

endendend

if parent(t)~=0,path=td=dist(t)%回溯最短路径

while t~=s,p=parent(t)path=[p path]t=pend

end

希望对你有用

是否可以解决您的问题？

/**************************************************************

* 给定一个带权有向图G = (V，E)，其中每条边的权是一个非负整数。*

* 另外还给定V中的一个顶点，称为源。现在我们要计算从源到所有其 *

* 他各顶点的最搜槐祥短路长度。这里路径长度是路上各边权之和。这个问 *

* 题通常称为单源最短路径问题。*

***************************************************************/

#include<iostream.h>

#define INFINITE 100

void main()

{

int j,i,n,k,t,**w,*s,*p,*d

cout<<"input the value of n:"

cin>>n

cout<<endl

d = new int[n]

s = new int[n]

p = new int[n]

w = new int*[n]

for(i = 0i <ni++)

{

w[i] = new int[n]

}

for(i = 0i <ni++)

for(j = 0j <nj++)

cin>>w[i][j]

for(s[0] = 1,i = 1i <ni++)

{

s[i] = 0

d[i] = w[0][i]

if(d[i] <INFINITE)

p[i]=0

else

p[i]=-1

}

for(i = 1i <ni++)

{

t = INFINITE

k = 1

for(j = 1j <nj++)

if((!s[j]) &&(d[j] <t))

{

t = d[j]

k = j

}

s[k]=1//point k join the S

for (j = 1j <nj++)

if((!s[j]) &&(d[j] >d[k] + w[k][j]))

{

d[j] = d[k] + w[k][j]

p[j] = k

}

}

cout<<"从源点到其它顶点的最短距离依次如下："

for(i=1i<ni++) cout<<d[i]<<" "

cout<<endl

}

/*********

顶点个数用n表示，这里给出的例子n=6

100 1 12 100 100 100

100 100 9 3 100 100

100 100 100 100 5 100

100 100 4 100 13 15

100 100 100 100 100 4

100 100 100 100 100 100

具体例子见 电子工明毁业出版社 《算法设计技巧世搏与分析》148页

************/

---