Dijkstra算法实现与分析

格式：doc
大小：132.50 KB
文档页数：14

下载文档原格式

/ 14

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Dijkstra’s算法设计与分析实验

1．Dijkstra’s算法:的实现。

注：本算法来自教材（英文版），在此就省略了，只给出具体实现的程序代码，采用Microsoft Visual C++ 6.0实现，并且图的存储结构为邻接表。

①本项目的组成结构如图所示

②各对应模块的功能如下：

asjacent(VNOde v,int a)：判断二接点是否相邻。

belong(int A[],int n,int p): 判断一个元素是否在指定数组中。

dijkstra(Vnode G[],int n):求最短路径问题的函数。

length(Vnode v,int a): 找出二相邻接点的长度。

main():主函数。

min(int r[],int Y[],int n):找出最小的元素的下标.

shanchu(int A[],int sum,int p):删除数组中值为p的元素(覆盖).

③对应完整程序：

#include

#define N 6 // 图的接点个数

typedef struct ANode

{ int adjvex;

struct ANode *nextarc;

int distance; //边的长度

}ArcNode;

typedef struct Vnode

{

ArcNode *firstarc;

}VNode;

int adjacent(VNode v,int a) //判断二接点是否相邻

{ ArcNode *arc=v.firstarc;

while(arc!=NULL)

{ if(arc->adjvex==a)

return 1;

arc=arc->nextarc;

}

return 0;

}

int length(VNode v,int a) //找出二相邻接点的长度

{ ArcNode *arc=v.firstarc;

while(arc!=NULL)

{ if(arc->adjvex==a)

return arc->distance;

arc=arc->nextarc;

}

return 0;

}

int min(int r[],int Y[],int n) //找出最小的元素的下标

{ int min=r[Y[0]],k=Y[0];

for(int i=1;i

if(r[Y[i]]

return k;

}

void shanchu(int A[],int sum,int p) //删除数组中值为p的元素(覆盖)

{ for(int i=0;i

{ if(p==A[i])

if(p!=A[sum-1])

{ for(int j=i;j

A[j]=A[j+1];

}

int belong(int A[],int n,int p) //判断一个元素是否在指定数组中

{ for(int i=0;i

if(p==A[i]) return 1;

return 0;

}

void dijkstra(VNode G[],int n)

{ int X[N]={0},Y[N-1],r[N],m=1,q=n-1; //m,q分别代表二数组中当前元素的个数ArcNode *arc;

for(int i=1;i

Y[i-1]=i;

r[0]=0;

for(int y=1;y

{ if(adjacent(G[0],y)) r[y]=length(G[0],y);

else r[y]=63535;

}

for(int j=0;j

{

y=min(r,Y,q);

m++;X[m-1]=y;

shanchu(Y,q,y);q--;

arc=G[y].firstarc;

while(arc!=NULL)

{ if(belong(Y,q,arc->adjvex) && (r[y]+length(G[y],arc->adjvex)adjvex]))

r[arc->adjvex]=r[y]+length(G[y],arc->adjvex);

arc=arc->nextarc;

}

for(i=0;i

cout<

}

void main(void)

{ VNode G[N];

ArcNode *p;