dis[j]=dis[w]+g->arcs[w][j]
应该写成：
if(vset[j] &&g->arcs[w][j]<MAXWEIGHT &&dis[w]+g->橘则arcs[w][j]<dis[j])
{
dis[j]=dis[w]+g->arcs[w][j]
path[j] = w// 这一句用来记录到点j的最册袜短路径的上一个节点是w。
}
另外，圆姿棚cout<<g->data[end].name这一句好像是多余的吧。
/* 用邻接矩阵表示的图的Dijkstra算法的源程序*/#include<stdio.h>
#define MAXVEX 100
typedef char VexType
typedef float AdjType
typedef struct
{ VexType vexs[MAXVEX]/* 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]/* 边信息 */
int n/* 图的顶点个数 */
}GraphMatrix
GraphMatrix graph
typedef struct {
VexType vertex/* 顶点信息 */
AdjType length/* 最短路径长度 */
int prevex/* 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点 */
}Path
Path dist[6]/* n为图中顶点个数*/
#define MAX 1e+8
void init(GraphMatrix* pgraph, Path dist[])
{
int idist[0].length=0dist[0].prevex=0
dist[0].vertex=pgraph->vexs[0]
pgraph->arcs[0][0]=1/* 表示顶点v0在集合U中 */
for(i=1i<pgraph->ni++) /* 初始化集合V-U中顶点的距离值 */
{ dist[i].length=pgraph->arcs[0][i]
dist[i].vertex=pgraph->vexs[i]
if(dist[i].length!=MAX)
dist[i].prevex=0
else dist[i].prevex= -1
}
}
void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvexAdjType min
init(&graph,dist)/* 初始化，此时集合猛斗桐U中只有枝坦顶点v0*/
for(i=1i<graph.ni++)
{ min=MAXminvex=0
for(j=1j<graph.nj++)
if( (graph.arcs[j][j]==0) &&(dist[j].length<min) ) /*在V-U中选出距离值最小顶点*/
{ min=dist[j].lengthminvex=j}
if(minvex==0) break/* 从v0没有路径可以通往集合V-U中的顶点 */
graph.arcs[minvex][minvex]=1/* 集合V-U中路径最小的销睁顶点为minvex */
for(j=1j<graph.nj++) /* 调整集合V-U中的顶点的最短路径 */
{ if(graph.arcs[j][j]==1) continue
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j]
dist[j].prevex=minvex
}
}
}
}
void initgraph()
{
int i,j
graph.n=6
for(i=0i<graph.ni++)
for(j=0j<graph.nj++)
graph.arcs[i][j]=(i==j?0:MAX)
graph.arcs[0][1]=50
graph.arcs[0][2]=10
graph.arcs[1][2]=15
graph.arcs[1][4]=5
graph.arcs[2][0]=20
graph.arcs[2][3]=15
graph.arcs[3][1]=20
graph.arcs[3][4]=35
graph.arcs[4][3]=30
graph.arcs[5][3]=3
graph.arcs[0][4]=45
}
int main()
{
int i
initgraph()
dijkstra(graph,dist)
for(i=0i<graph.ni++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex)
return 0
}
}
}
}
void initgraph()
{
int i,j
graph.n=6
for(i=0i<graph.ni++)
for(j=0j<graph.nj++)
graph.arcs[i][j]=(i==j?0:MAX)
graph.arcs[0][1]=50
graph.arcs[0][2]=10
graph.arcs[1][2]=15
graph.arcs[1][4]=5
graph.arcs[2][0]=20
graph.arcs[2][3]=15
graph.arcs[3][1]=20
graph.arcs[3][4]=35
graph.arcs[4][3]=30
graph.arcs[5][3]=3
graph.arcs[0][4]=45
}
int main()
{
int i
initgraph()
dijkstra(graph,dist)
for(i=0i<graph.ni++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex)
return 0
}
这个稍作改动就可以了。
#include<fstream>#define MaxNum 765432100
using namespace std
ifstream fin("Dijkstra.in")
ofstream fout("Dijkstra.out")
int Map[501][501]
bool is_arrived[501]
int Dist[501],From[501],Stack[501]
int p,q,k,Path,Source,Vertex,Temp,SetCard
int FindMin()
{
int p,Temp=0,Minm=MaxNum
for(p=1p<=Vertexp++)
if ((Dist[p]<Minm)&&(!is_arrived[p]))
{
Minm=Dist[p]
Temp=p
}
return Temp
}
int main()
{
memset(is_arrived,0,sizeof(is_arrived))
fin >>Source >没埋腊>Vertex
for(p=1p<=Vertexp++)
for(q=1q<=Vertexq++)
{
fin >>Map[p][q]
if (Map[p][q]==0) Map[p][q]=MaxNum
}
for(p=1p<=Vertexp++)
{
Dist[p]=Map[Source][p]
if (Dist[p]!=MaxNum)
From[p]=Source
else
From[p]=p
}
is_arrived[Source]=true
SetCard=1
do
{
Temp=FindMin()
if (Temp!=0)
{
SetCard=SetCard+1
is_arrived[Temp]=true
for(p=1p<=Vertexp++)
if ((Dist[p]>Dist[Temp]+Map[Temp][p])&&(!is_arrived[p]))
{
Dist[p]=Dist[Temp]+Map[Temp][p]
From[p]=Temp
}
}
else
break
}
while (SetCard!=Vertex)
for(p=1p<=Vertexp++)
if(p!=Source)
{
fout <<"========================\n"
fout <<"Source:" <<Source <<"\nTarget:" <<p <<'\n'
if (Dist[p]==MaxNum)
{
fout <<"Distance:" <<"Infinity\n"枯滑
fout <<"Path:No Way!"
}
else
{
fout <<"Distance:" <<Dist[p] <<'\n'
k=1
Path=p
while (From[Path]!=Path)
{
Stack[k]=Path
Path=From[Path]
k=k+1
}
fout <<"Path:" <<Source
for(q=k-1q>=1q--)
fout <<液搏 "-->" <<Stack[q]
}
fout <<"\n========================\n\n"
}
fin.close()
fout.close()
return 0
}
Sample Input
2
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 00
00 70 50 00 10 00 00
00 00 00 00 00 00 00
Sample Output
========================
Source:2
Target:1
Distance:20
Path:2-->1
========================
========================
Source:2
Target:3
Distance:25
Path:2-->3
========================
========================
Source:2
Target:4
Distance:50
Path:2-->1-->4
========================
========================
Source:2
Target:5
Distance:50
Path:2-->3-->5
========================
========================
Source:2
Target:6
Distance:60
Path:2-->3-->5-->6
========================
========================
Source:2
Target:7
Distance:Infinity
Path:No Way!
========================
示例程序及相关子程序：
void Dijkstra(int n,int[] Distance,int[] iPath)
{
int MinDis,u
int i,j
//从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance[]
for(i=0i<VerNumi++)
{
Distance=Arc[n,i]
Visited=0
}//第n个顶点被访问，因为第n个顶点是开始点
Visited[n]=1
//找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。
//相当于寻找u点，这个点不是开始点n
for(i=0i<VerNumi++)
{
u=0
MinDis=No
for(j=0j<VerNumj++)
if(Visited[j] == 0&&(Distance[j]<MinDis))
{
MinDis=Distance[j]
u=j
}
//如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2
//找完了，MinDis等于不连接，则返回。这种情况类似V5。
if(MinDis==No) return
//确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。
Visited[u]=1
//寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，VerNum]。
//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，则Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]
//实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是：
//如果(Distance[u] + Arc[u,j]) <= Distance[j] 则：
//Distance[j] = Distance[u] + Arc[u, j]；
//而iPath[]保存了u点的编号；
//同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3
for(j=0j<VerNumj++)
if(Visited[j]==0&&Arc[u,j]<No&&u!= j)
{
if ((Distance[u] + Arc[u,j]) <= Distance[j])
{
Distance[j] = Distance[u] + Arc[u, j]
Visited[j]=0
iPath[j] = u
}
}
}
}
//辅助函数
void Prim()
{
int i,m,n=0
for(i=0i<VerNumi++)
{
Visited=0
T=new TreeNode()
T.Text =V
}
Visited[n]++
listBox1.Items.Add (V[n])
while(Visit()>0)
{
if((m=MinAdjNode(n))!=-1)
{
T[n].Nodes.Add(T[m])
n=m
Visited[n]++
}
else
{
n=MinNode(0)
if(n>0) T[Min2].Nodes.Add(T[Min1])
Visited[n]++
}
listBox1.Items.Add (V[n])
}
treeView1.Nodes.Add(T[0])
}
void TopoSort()
{
int i,n
listBox1.Items.Clear()
Stack S=new Stack()
for(i=0i<VerNumi++)
Visited=0
for(i=VerNum-1i>=0i--)
if(InDegree(i)==0)
{
S.Push(i)
Visited++
}
while(S.Count!=0)
{
n=(int )S.Pop()
listBox1.Items.Add (V[n])
ClearLink(n)
for(i=VerNum-1i>=0i--)
if(Visited==0&&InDegree(i)==0)
{
S.Push(i)
Visited++
}
}
}
void AOETrave(int n,TreeNode TR,int w)
{
int i,w0
if(OutDegree(n)==0) return
for(i=0i<VerNumi++)
if((w0=Arc[n,i])!=0)
{
listBox1.Items.Add (V+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString())
TreeNode T1=new TreeNode()
T1.Text =V+" [W="+(w+w0).ToString()+"]"
TR.Nodes.Add(T1)
AOETrave(i,T1,w+w0)
}
}
void AOE()
{
int i,w=0,m=1
TreeNode T1=new TreeNode()
for(i=0i<VerNumi++)
{
Visited=0
}
T1.Text =V[0]
listBox1.Items.Add ("双亲表示法显示这个生成树：")
listBox1.Items.Add ("V\tW\tID\tPID")
for(i=0i<VerNumi++)
{
if((w=Arc[0,i])!=0)
{
listBox1.Items.Add (V+"\t"+w.ToString()+"\t"+i.ToString()+"\t0")
TreeNode T2=new TreeNode()
T2.Text=V+" [W="+w.ToString()+"]"
AOETrave(i,T2,w)
T1.Nodes.Add (T2)
listBox1.Items.Add("\t\t树"+m.ToString())
m++
}
}
treeView1.Nodes.Clear()
treeView1.Nodes.Add (T1)
}
int IsZero()
{
int i
for(i=0i<VerNumi++)
if(LineIsZero(i)>=0) return i
return -1
}
int LineIsZero(int n)
{
int i
for(i=0i<VerNumi++)
if (Arc[n,i]!=0) return i
return -1
}
void DepthTraverse()
{
int i,m
for(i=0i<VerNumi++)
{
Visited=0
T=new TreeNode()
T.Text =V
R=0
}
while((m=IsZero())>=0)
{
if(Visited[m]==0)
{
listBox1.Items.Add (V[m])
R[m]=1
}
Visited[m]++
DTrave(m)
}
for(i=0i<VerNumi++)
{
if(R==1)
treeView1.Nodes.Add (T)
}
}
void DTrave(int n)
{
int i
if (LineIsZero(n)<0) return
for(i=VerNum-1i>=0i--)
if(Arc[n,i]!=0)
{
Arc[n,i]=0
Arc[i,n]=0
if(Visited==0)
{
listBox1.Items.Add (V)
T[n].Nodes.Add (T)
R=0
}
Visited++
DTrave(i)
}
}
void BreadthTraverse()
{
int i,m
for(i=0i<VerNumi++)
{
Visited=0
T=new TreeNode()
T.Text =V
R=0
}
while((m=IsZero())>=0)
{
if(Visited[m]==0)
{
listBox1.Items.Add (V[m])
R[m]=1
}
Visited[m]++
BTrave(m)
}
for(i=0i<VerNumi++)
{
if(R==1)
treeView1.Nodes.Add (T)
}
}
void BTrave(int n)
{
int i
Queue Q=new Queue()
Q.Enqueue(n)
while(Q.Count!=0)
{
for(i=0i<VerNumi++)
{
if(Arc[n,i]!=0)
{
Arc[n,i]=0
Arc[i,n]=0
if(Visited==0)
{
listBox1.Items.Add(V)
T[n].Nodes.Add (T)
R=0
}
Visited++
Q.Enqueue(i)
}
}
n=(int )Q.Dequeue()
}
}
int MinNode(int vn)
{
int i,j,n,m,Min=No
n=-1m=-1
for (i=vni<VerNumi++)
for(j=0j<VerNumj++)
if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited==0&&Visited[j]==1)
{
Min=Arc[i,j]n=im=j
}
Min1=nMin2=m
return n
}
int MinAdjNode(int n)
{
int i,Min,m
Min=Nom=-1
for(i=0i<VerNumi++)
if(Arc[n,i]!=No&&Visited==0&&Min>Arc[n,i]&&Visited[n]==1)
{
Min=Arc[n,i]m=i
}
return m
}
int Visit()
{
int i,s=0
for(i=0i<VerNumi++)
if(Visited==0) s++
return s
}
[编辑本段]dijkstra算法的Pascal实现：
program dijkstra
var
a:array[1..100,1..100]of integer
flag:array[1..100]of boolean
w,x,n,i,j,min,minn:integer
begin
readln(n)
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j])
readln
end
fillchar(flag,sizeof(flag),false)
flag[1]:=true
minn:=1
for x:=2 to n do
begin
min:=32767
for i:=2 to n do
if (a[1,i]<min)and(flag=false) then
begin
min:=a[1,i]
minn:=i
end
flag[minn]:=true
for j:=1 to n do
if (j<>minn) and (a[1,minn]+a[minn,j]<a[1,j]) and(flag[j]=false) then
a[1,j]:=a[1,minn]+a[minn,j]
end
for i:=1 to n do
write(a[1,i],' ')
end.
4
0 100 30 999
100 0 99 10
30 99 0 99
999 10 99 0
程序输出：0 100 30 110
dijkstra算法的MATLAB实现：
clear
clc
M=10000
a(1,:)=[0,50,M,40,25,10]
a(2,:)=[zeros(1,2),15,20,M,25]
a(3,:)=[zeros(1,3),10,20,M]
a(4,:)=[zeros(1,4),10,25]
a(5,:)=[zeros(1,5),55]
a(6,:)=zeros(1,6)
a=a+a'
pb(1:length(a))=0pb(i)=1index1=1index2=ones(1,length(a))
d(1:length(a))=Md(i)=0temp=1
while sum(pb)<length(a)
tb=find(pb==0)
d(tb)=min(d(tb),d(temp)+a(temp,tb))
tmpb=find(d(tb)==min(d(tb)))
temp=tb(tmpb(i))
pb(temp)=1
index1=[index1,temp]
index=index1(find(d(index1)==d(temp)-a(temp,index1)))
if length(index)>=2
index=index(1)
end
index2(temp)=index
end
d, index1, index2
matlab编程
function [s,d]=minroute(i,m,w,opt)
% 图与网络论中求最短路径的dijkstra算法M函数
% 格式[s,d]=minroute(i,m,w,opt)
if nargin<4,opt=0end
dd=[]tt=[]ss=[]ss(1,1)=iv=1:mv(i)=[]
dd=[0i]kk=2[mdd,ndd]=size(dd)
while~isempty(v)
[tmpd,j]=min(w(i,v))tmpj=v(j)
for k=2:ndd
[tmp2,jj]=min(dd(1,k)+w(dd(2,k),v))
tmp2=v(jj)tt(k-1,:)=[tmp1,tmp2,jj]
end
tmp=[tmpd,tmpj,jtt][tmp3,tmp4]=min(tmp(,1))
if tmp3==tmpd
ss(1:2,kk)=[itmp(tmp4,2)]
else,tmp5=find(ss(:,tmp4)~=0)tmp6=length(tmp5)
if dd(2,tmp4)=ss(tmp6,tmp4)
ss(1:tmp6+1,kk)=[ss(tmp5,tmp4)tmp(tmp4,2)]
else,ss(1:3,kk)=[idd(2,tmp4)tmp(tmp4,2)]
endend
dd=[dd,[tmp3,tmp(tmp4,2)]]v(tmp(tmp4,3))=[]
[mdd,ndd]=size(dd)kk=kk+1
end
if opt==1
[tmp,t]=sort(dd(2,:))s=ss(:t)d=dd(1,t)
else,s=ssd=dd(1,:)
end
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）