没有合适的资源?快使用搜索试试~ 我知道了~
首页C++求所有顶点之间的最短路径(用Dijkstra算法)
C++求所有顶点之间的最短路径(用Dijkstra算法)
5星 · 超过95%的资源 24 下载量 14 浏览量
更新于2023-03-16
评论 1
收藏 105KB PDF 举报
主要为大家详细介绍了C++用Dijkstra算法求所有顶点之间的最短路径,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
资源详情
资源评论
资源推荐
C++求所有顶点之间的最短路径(用求所有顶点之间的最短路径(用Dijkstra算法)算法)
主要为大家详细介绍了C++用Dijkstra算法求所有顶点之间的最短路径,文中示例代码介绍的非常详细,具有一
定的参考价值,感兴趣的小伙伴们可以参考一下
本文实例为大家分享了C++求所有顶点之间最短路径的具体代码,供大家参考,具体内容如下
一、思路:一、思路: 不能出现负权值的边不能出现负权值的边
(1)轮流以每一个顶点为源点,重复执行Dijkstra算法n次,就可以求得每一对顶点之间的最短路径及最短路径长度,总的执
行时间为O(n的3次方)
(2)另一种方法:用Floyd算法,总的执行时间为O(n的3次方)(另一文章会写)
二、实现程序:二、实现程序:
1.Graph.h:有向图
#ifndef Graph_h
#define Graph_h
#include <iostream>
using namespace std;
const int DefaultVertices = 30;
template <class T, class E>
struct Edge { // 边结点的定义
int dest; // 边的另一顶点位置
E cost; // 表上的权值
Edge<T, E> *link; // 下一条边链指针
};
template <class T, class E>
struct Vertex { // 顶点的定义
T data; // 顶点的名字
Edge<T, E> *adj; // 边链表的头指针
};
template <class T, class E>
class Graphlnk {
public:
const E maxValue = 100000; // 代表无穷大的值(=∞)
Graphlnk(int sz=DefaultVertices); // 构造函数
~Graphlnk(); // 析构函数
void inputGraph(); // 建立邻接表表示的图
void outputGraph(); // 输出图中的所有顶点和边信息
T getValue(int i); // 取位置为i的顶点中的值
E getWeight(int v1, int v2); // 返回边(v1, v2)上的权值
bool insertVertex(const T& vertex); // 插入顶点
bool insertEdge(int v1, int v2, E weight); // 插入边
bool removeVertex(int v); // 删除顶点
bool removeEdge(int v1, int v2); // 删除边
int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点
int getNextNeighbor(int v,int w); // 取顶点v的邻接顶点w的下一邻接顶点
int getVertexPos(const T vertex); // 给出顶点vertex在图中的位置
int numberOfVertices(); // 当前顶点数
private:
int maxVertices; // 图中最大的顶点数
int numEdges; // 当前边数
int numVertices; // 当前顶点数
Vertex<T, E> * nodeTable; // 顶点表(各边链表的头结点)
};
// 构造函数:建立一个空的邻接表
weixin_38624315
- 粉丝: 7
- 资源: 921
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- stc12c5a60s2 例程
- Android通过全局变量传递数据
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论5