求该加权有向图的最短路径径

来源：蜘蛛抓取(WebSpider) 时间：2017-08-01 21:39 标签： 无权有向图最短路径
知识点讲解:
知识点章节：
作业互助QQ群：(小学)、(初中)、(高中)带权有向图（最短路径算法Dijkstra算法）
1.Dijkstra
适用条件&范围：
a)&&&单源最短路径(从源点s到其它所有顶点v);
b)&&&有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
c)&&&所有边权非负(任取(i,j)∈E都有Wij≥0);
算法描述：
在带权图中最常遇到的问题就是，寻找两点间的最短路径问题。
解决最短路径问题最著名的算法是Djikstra算法。这个算法的实现基于图的邻接矩阵表示法，它不仅能够找到任意两点的最短路径，还可以找到某个指定点到其他所有顶点的最短路径。
此算法的基本思想是：
1&选中指定的顶点，列出此顶点到其他的顶点的权值，不相邻的为无穷大
2&从以上权值中选出最小值，此最小值就是起始点到对应顶点的最短路径，并标记这个对应顶点
将起始点到其他未标记的顶点的直接距离与起始点到刚才标记顶点加上标记顶点到其他顶点距离的和比较，如果&&&&
后者小，则更新对应的权值。
程序代码如下：
#include &iostream&
#include &iomanip&
#include "Graph.h"
void main()
&&& int i,
&& "输入你所输入的有向带权图的顶点个数: ";
&&& adjmatrix
InitMatrix(g);
CreateMatrix(g);
&& "你输入的有向带权图的邻接矩阵表示为: "
PrintMatrix(g, n);
&&& int * d =
new int [n];
&&& edgenode
** path = new edgenode * [n];
&& "请输入你要输入的源点: ";
Dijkstra(g, d, path, i, n);
PrintPath(d, path, i, n);
//***********Graph.h**********************
#define MaxVerNum 20
#define MaxValue 10000
typedef int
adjmatrix[MaxVerNum][MaxVerNum];&&&&
//邻接矩阵的类型定义
typedef struct Node
&&& struct
//指针数组path[]基类型定义
//初始化邻接矩阵表示的有向带权图
void InitMatrix(adjmatrix G)
&&& for(i =
0; i & MaxVerN i++)
for(j = 0; j & MaxVerN j++)
&&&&&&&&&&
G[i][j] = MaxV
//建立邻接矩阵表示的有权带向图(即通过输入图的每条边建立图的邻接矩阵)
void CreateMatrix(adjmatrix G)
&&& int i, j,
&& "请输入顶点和相应的权值: "
&&& while(i
//输出邻接矩阵表示的有向带权图(即输出图的每条边)
void PrintMatrix(adjmatrix G, int n)
&&& int i,
&&& for(i =
0; i & i++)
for(j = 0; j & j++)
&&&&&&&&&&
if(G[i][j] == MaxValue)
&&&&&&&&&&&&&
cout && setiosflags(ios::left)
&& setw(5)
&&&&&&&&&&
&&&&&&&&&&&&&
cout && setiosflags(ios::left)
&& setw(5)
&& G[i][j];
void Path(edgenode * path[], int m, int j)
&&& edgenode
* p, * q, *s;
&&& while(p
path[j] = p-&
p = path[j];
&&& while(p
q-&adjvex = p-&
if(path[j] == NULL)
&&&&&&&&&&
&&&&&&&&&&
&&& q = new
q-&adjvex =
q-&next = NULL;
//求最短路径的Dijkstral算法
void Dijkstra(adjmatrix GA, int dist[], edgenode *path[], int i,
&&& int j, k,
&&& bool * s
= new bool[n];
&&& for(j =
0; j & j++)
if(j == i)
&&&&&&&&&&
&&&&&&&&&&
dist[j] = GA[i][j];
if(dist[j] & MaxValue
&& j != i)
&&&&&&&&&&
edgenode * p1 =
&&&&&&&&&&
edgenode * p2 =
&&&&&&&&&&
p1-&adjvex =
&&&&&&&&&&
p2-&adjvex =
&&&&&&&&&&
p2-&next = NULL;
&&&&&&&&&&
p1-&next = p2;
&&&&&&&&&&
path[j] = p1;
&&&&&&&&&&
path[j] = NULL;
&&& for(k =
1; k &= n-2; k++)
for(j = 0; j & j++)
&&&&&&&&&&
if(s[j] == false && dist[j]
&&&&&&&&&&
&&&&&&&&&&&&&
w = dist[j];
&&&&&&&&&&&&&
&&&&&&&&&&
if(m != i)
&&&&&&&&&&
&&&&&&&&&&
for(j = 0; j & j++)
&&&&&&&&&&
if(s[j] == false && dist[m] +
GA[m][j] & dist[j])
&&&&&&&&&&
&&&&&&&&&&&&&
dist[j] = dist[m]+GA[m][j];
&&&&&&&&&&&&&
Path(path, m, j);
&&&&&&&&&&
&&& delete
//输出从源点到每个顶点的最短路径及长度的函数
void PrintPath(int dist[], edgenode * path[], int i, int n)
&&& for(j =
0; j & j++)
if(i != j)
&&&&&&&&&&
cout && "顶点v"
"到顶点v" && j
&& "的最短路径的长度为 "
&&&&&&&&&&&&&
&& dist[j]
&& ", 最短路径为: ";
&&&&&&&&&&
edgenode * p = path[j];
&&&&&&&&&&
while(p != NULL)
&&&&&&&&&&
&&&&&&&&&&&&&
cout && setw(4)
&&&&&&&&&&&&&
&&&&&&&&&&
&&&&&&&&&&
程序运行结果:
输入你所输入的有向带权图的顶点个数: 6
请输入顶点和相应的权值:
你输入的有向带权图的邻接矩阵表示为:
Inf& Inf& Inf&
请输入你要输入的源点: 0
顶点v0到顶点v1的最短路径的长度为 10, 最短路径为:
顶点v0到顶点v2的最短路径的长度为 12, 最短路径为:
顶点v0到顶点v3的最短路径的长度为 22, 最短路径为:
顶点v0到顶点v4的最短路径的长度为 29, 最短路径为:
顶点v0到顶点v5的最短路径的长度为 20, 最短路径为:
Press any key to continue
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
应用邻接矩阵求有向图的最短路径
下载积分：652
内容提示：应用邻接矩阵求有向图的最短路径
文档格式：PDF|
浏览次数：0|
上传日期： 22:49:10|
文档星级：
全文阅读已结束，如果下载本文需要使用
 652 积分
下载此文档
该用户还上传了这些文档
应用邻接矩阵求有向图的最短路径
官方公共微信有向图的最短路径_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
有向图的最短路径
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢以下试题来自：
单项选择题 下面关于有向图的运算的叙述中，哪个（些）是正确的？（） Ⅰ．求有向图结点的拓扑序列，其结果必定是唯一的 Ⅱ．求两个指向结点间的最短路径，其结果必定是唯一的 Ⅲ．求事件结点网络的关键路径，其结果必定是唯一的
D．都不正确
为您推荐的考试题库
你可能感兴趣的试题
C．Ⅰ、Ⅱ和Ⅳ
A．计划阶段、开发阶段、运行阶段&
B．计划阶段、编程阶段、测试阶段&
C．总体设计、详细设计、编程调试&
D．需求分析、功能定义、系统设计
4A．7B．9C．12D．165
A．电子邮件服务器
B．WWW服务器
C．文件服务器
D．FTP服务器
热门相关试卷
最新相关试卷

我要回帖

更多关于 无权有向图最短路径 的文章

 

随机推荐