通信网基础及应用课程设计--基于Vc++最短路径Dijkstra算法的实现.doc
文本预览下载声明
课程设计说明书 NO.1
基于Vc++最短路径Dijkstra算法的实现
1.课程设计的目的
为了巩固“通信网基础及应用”课程学到的相关知识,通过对本课程所学知识的综合运用,使学生融会贯通课程中所学的理论知识,初步;
2.设计方案论证
2.1 问题描述
给定一个带权向图 G=(V,E) ,其中每条边的权是一个非负实数。
另外,还给定 V 中的一个项点,称为源。
现在我们要计算从源到所有其他各项点的最短路径长度。
这里的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。 算法介绍 顶点的最短路径。算法描述
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。 初始时,源点s的路径长度值被赋为0(d[s]=0),同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有 顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路 径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行 到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S初始状态为空,而后每一步 都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。相关问题和算法
在Dijkstra 算法的基础上作一些改动,可以扩展其功能。
OSPF(open shortest path first, 开放最短路径优先)算法是Dijkstra算法在网络路由中的一个具体实现。
与Dijkstra算法不同,Bellman-Ford算法可用于具有负花费边的图,只要图中不存在总花费为负值且从源点 s 可达的环路(如果有这样的环路,则最短路径不存在,因为沿环路循环多次即可无限制的降低总花费)。
与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem),它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的;换言之,与最短路径问题不同,旅行商问题不太可能具有多项式时间算法。
如果有已知信息可用来估计某一点到目标点的距离,则可改用A*算法 ,以减小最短路径的搜索范围。
另外,用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”。 最常用的路径算法有:
Dijkstra算法 SPFA算法
Bellman-Ford算法 Floyd-Warshall算法 Johnson算法
所谓单源最短路径问题是指:已知图G=(V,E),我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。#includeiostream.h
// 定义 状态代码 及 数据类型
#define NULL 0
#define OK 1
#define ERROR 0
#define INFINITY 255
#define MAX_VERTEX_NUM 20
typedef int Status;
typedef int ElemType;
// ----------------------- 队列结构 -------------------------
// 节点存储结构
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;
// 队列
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
// 初始化队列
Status InitQueue(LinkQueue Q){
Q.front=Q.rear=new QNode;
if(!Q.front)
return ERROR;
Q.front-next=NULL;
return OK;
}
// 入队
Status EnQueue(LinkQueue Q,ElemType e){
QueuePtr p=NULL;
p=new QNode;
if(!p)
return ERROR;
p-data=e;
p-next=N
显示全部