C++ Dijkstra算法之求图中任意两顶点的最短路径
程序员文章站
2022-06-25 08:00:48
dijkstra算法是图中找任意两点中最短路径的一种经典算法。重点的步骤总结如下：1.算法采用了并查集 (之后都叫它为 最短路径顶点集 ):即每次都找离开始顶点距离最短的顶点，然后把该顶点加入最短路径...
dijkstra算法是图中找任意两点中最短路径的一种经典算法。
重点的步骤总结如下：
1.算法采用了并查集 (之后都叫它为 最短路径顶点集 ):即每次都找离开始顶点距离最短的顶点，然后把该顶点加入最短路径顶点集中(已经加入最短路径顶点集里的那些顶点 下一次就会跳过它了，并且，在顶点集里 任意两个顶点间的距离 都已经是最短)
2.用来记录从源点(开始顶点) 到vi (0<=i<=numvertices) 的最短距离 的数组dist[numvertices] ,并且这个数组的元素值是会不断变化的，为什么呢，因为，这个最短距离无非两种情况。
第一种：开始顶点v直接到达目的顶点x的距离。
第二种：开始顶点v先到达中间顶点vk(vk可能不止一个)再到目的顶点的距离。
要么是第一种情况最短，要么是第二种情况最短，因此需要再这两者间选择一个最小值作为最短路径。
dist[w] = min {dist[w] ，dist[k] + this->getweight(k,w)};
3.路径数组path[],这个数组 保存了从源点到终点vi 的最短路径上该顶点的前驱顶点的序号，即：会记录最短路径 某个顶点的上一个 顶点是什么，比如说 path[4]的值是2,那么 4的上一个顶点 就是2 ,path[2]的顶点比如是3 那么2的上一个顶点就是3 ,继续， 如果path[3]是0那么 这个路径为: ， 因此，当dijkstra算法结束的时候，我们只需要从最后那个顶点开始 path[endvertexce] 就可以得到它上一个顶点的下标，然后一直找，直到找到源点，那么这个路径就输出完了.
dijkstra算法求带权有向图单元最短路径的示例过程图如下：
图a为 本次的示例图，然后假如要从v0出发，去找顶点v4的最短距离.首先，我们可以看到图b 伸出三条虚线，是什么意思呢？就是因为v0 和这三个顶点都连通，然后，找一个最短和v0相连的顶点，发现是v1，权值是10，然后接下来的要做什么呢？？接下来就是重点了，要从v1出发，去寻找所有与v1 相连的顶点，如果源点到 v1 后再到这些顶点的距离 比 源点直接到 这些 和v1相连的顶点 的距离 短的话
就要重新修改v0到 vx的值(x为任意与v1相连的顶点),即v0—>v1—>v2，一开始v0不能直接到v2所以dist[2]=∞,但是v0->v1->v2的值却为60,因此dist[2]的值就改为60,即v0通过“某条路径”抵达 v2的当前最短路径就是60，为什么说是当前呢，因为等下可能还有其他 未加入最短路径顶点集 的某个顶点，他可能从源点，再经过它 再到v2 ，比 从源点出发到 v1 再到v2的距离更小！(比如说v3)。接着重复以上操作:在未加入"最短路径顶点集" 里 找一个离源点最近的 顶点，然后让它加入”最短路径顶点集“里 因为刚才加入的是v1，它的权值是10 ，然后v1里没有能够到达v3的边，所以，v3的值没有改变，如果v3的值要改变的话:当且仅当从源点 到最小权值顶点再到 v3 因此，v0到v3已经是最小的路径了，因此，把它加入 最短路径顶点集里， 加入到最短路径顶点集里，任意两个顶点之间的距离 都已经是最短路径， v3加到顶点集之后要做的事情 还是和刚才那样：不断去寻找和它相连接的顶点vx，然后比较 v0直接到vx的距离是否比 v0 先到v3再到 vx的距离大，如果是，做两件事情:
① 修改dist[x] 的值(即v0通过某一条路径到达vx的最短路径 这里如果前提条件成立 这条路径为: v0—>v3—>vx).
②修改路径数组path[x]=index(v3)=3 （下标0对应v0,下标1对应v1…），即让x这个位置的顶点的前驱的下标索引为3，即v3的下标索引.
dijkstra算法的思想就是像上述一样，未完成的步骤留给读者完成。
具体测试代码如下(有些代码与dijkstra算法无关，代码是基于之前实现的代码，如果是devc++ 编译器，可以按住ctrl +鼠标左键 点击主函数的测试代码的函数，可以跳到对应 的函数代码体，见谅见谅.)
本次路径的输出利用了栈，使得路径可以按从起点到终点 按顺序 输出。
本次测试图如下:
代码如下:
#include<iostream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const long long int maxweight = rand_max; //无穷大的值
const int defaultvertices = 30; //最大顶点数不妨设为30
template <class t, class e>
class graph {
protected:
int maxvertices=10;//图中最大顶点数
int numvertices=0;//图中当前顶点数
int numedges=0;//图中当前边数
bool direction=false;//图中边的是否有方向
bool withcost=false;//图中的边是否带权
//返回顶点名vertex的序号(从0开始)
int getvertexpos (t vertex);
public:
void dfs (const t& v)
{
}
void bfs (const t& v)
{
}
graph(int sz , bool direct, bool cost); //构造函数
~graph()//析构函数
{}
//析构函数
bool graphempty () const //判图是否为空，因为不需要修改，因此设置为常成员函数
{
return numedges == 0;
}
bool graphfull() const; //判图是否为满
//返回图中当前顶点数
int numberofvertices ()
{
return numvertices;
}
//返回图中当前边数
int numberofedges ()
{
return numedges;
}
//取回序号为 i 的顶点值(顶点名)
virtual t getvalue (int i){
}
//取顶点序号为v1,v2的边上权值
virtual e getweight (int v1, int v2){
}
//取顶点 v 的第一个邻接顶点序号
virtual int getfirstneighbor (int v){
}
//返回顶点 v 和邻接顶点 w 的下一个邻接顶点序号
virtual int getnextneighbor (int v, int w){
}
//插入新顶点, 点名为vertex
virtual bool insertvertex (const t vertex){
}
//插入新边(v1,v2), 权值cost
virtual bool insertedge (t v1, t v2, e cost){
}
//删除名为 v 的顶点和所有与它相关联的边
virtual bool removevertex (t v){
}
//在图中删除边(v1,v2)
virtual bool removeedge (t v1, t v2){
}
};
template<class t , class e>
graph<t,e>::graph (int sz , bool direct, bool cost)
{
sz = defaultvertices, direct=false, cost=false;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
template <class t, class e> //
class edge_vertices { //边结点的类定义
public:
int dest; //边的邻接(终)点序号
e cost; //边上的权值
edge_vertices<t, e>* link;//下一个连接顶点
edge_vertices (int num=0, edge_vertices<t, e>* next=null, e weight=null) //构造函数
: dest (num), link (next), cost (weight) { }
bool operator != (edge_vertices<t, e>& r) const
{ return dest != r.dest; } //重载!=运算符,判边不等
};
template <class t, class e>
class vertex { //顶点的类定义
public:
t data; //源顶点的名字(数据)
edge_vertices<t, e>* next=null; //next指针用来连接顶点
};
//邻接表图的类定义继承图类
template <class t, class e>
class graphlnk : public graph<t, e>{
public:
void enter (void); //输入图中顶点和边信息
void print (void); //输出图中顶点和边信息
//源顶点表 (各边链表的源顶点)
vertex<t, e>* nodetable;
int *path;
int *dist;
//返回名为vertex的顶点在图中的序号(从0开始)，
//若未找到，则返回-1
int getvertexpos (const t vertx) //找到目标顶点所在的序号 期中 vertx 参数为string 类型
{ for (int i = 0; i < this->numvertices; i++)
if (nodetable[i].data == vertx) return i;
return -1;
} //构造函数
graphlnk( int sz=defaultvertices, bool direct=false, bool cost=false );
~graphlnk(); //析构函数
t getvalue (int i) { //取序号为 i 的顶点名
return (i >= 0 && i < this->numvertices) ?
nodetable[i].data : null;
}
e getweight (int v1, int v2); //取边(v1,v2)权值
bool insertvertex (const t& vertex); //插入名为vertex的新顶点
bool removevertex (int v); //删除序号为 v 的顶点
bool insertedge (t in ,t out, e cost); //插入新边
bool removeedge (int v1, int v2); //删除边(v1,v2)
int getfirstneighbor (int v);//取顶点v的首邻接顶点 ###本次代码这两条都没有用到
int getnextneighbor (int v, int w);//取w下一邻接点 ###本次代码这两条都没有用到
void dfs(const t &v);
void bfs(const t &v);
void dfs (int v, bool visited[]);
void bfs(int v , bool visited[]);
void connected_component();
void dijkstra (int v );
void print(int v, int w);
};
// 输出顶点 v 到顶点 w 的最短路径
//和最短路径长度。int* path;
// e** dist; 为类数据成员
template<typename t, typename e>
void graphlnk<t,e>::print(int v, int w)//输出从v 到w 的最短路径
{ //因为v和w都是 int 型,即输入类型的下标，因此，要用getvalue 获得原来的输入的顶点名字
cout<<"始顶点 "<<this->getvalue(v)<<" 到终顶点 "<<this->getvalue(w)<<" 的最短路径为:"<<endl;
int current=w, previous;
stack<char > road;//定义一个char类型的栈，因为是用顶点回溯 (即从 最后的一个顶点 往前找前驱顶点的，因此我们可以用栈(后进先出的特性))
//用栈后进先出的特性可以 在出栈的时候 按顺序输出从 开始顶点到目的顶点的 路径 ，如果对输出没有要求的话就不需要栈，可以直接输出
//不过输出的结果会倒置(从目的顶点 一步一步往回走 ，直到找到开始顶点)
stack<int >road_weight;//如果 顶点 要按顺序输出，还想输出 这两个顶点间的权值的话，那么这些权值也是倒置的，因此权值也需要利用栈的特性输出
road.push(this->getvalue(w)[0]);//因为this->getvalue(w) 返回的是一个string 类型， 本次测试的顶点都是要么是单个数字名字，或者单个字母名字
// 因为是char 类型，因此只能单个字母进去，所以this->getvalue(w)[0] 就是取第一个 字母/数字
while( current!=v )//如果这个顶点不等于 开始顶点的话
{
previous=path[current];//找它的上一个顶点
road.push(this->getvalue(path[current])[0]);//名字入栈
road_weight.push(this->getweight(previous,current));//权值入栈
current=previous;
}
string p;//string 变量 p 用来记录前面的顶点和 做临时变量
string e;//string 变量 e 用来输出顶点名字
int q;
int x=1;//一个标志
int i = 1;//第i步
while(road.empty()!=true)
{
//这个if 语句只运行一次，为什么呢，考虑到 奇数个顶点的话，那么，最短路径至少有两个顶点，如果第一次就把顶点输出完了
//那么后面的if语句都不会运行了，但是如果 是奇数个顶点呢？ 奇数个顶点的话，程序编译不会出错，但是运行会中断， 即栈已经空了，不能弹栈了
//因此，执行一次这个if语句 就开始 对顶点一个 一个的弹栈，而不是 两个两个的弹
if(x)
{
p=road.top();
road.pop();
q=road_weight.top();
road_weight.pop();
e=road.top();
road.pop();
x=0;//让if 语句为假
cout<<"第"<<i++<<"步为: "<<"顶点"<<p<<"-->到顶点"<<e<<" 长度为: "<<q<<endl;
}
if(road.empty()!=true)//如果栈不为空
{
p=e;//因为这个p在后面不再 用来接收 栈弹出的顶点，而是充当一个临时变量-------用上一个顶点 的末顶点 进行覆盖
e=road.top();//取栈首顶点
road.pop();// 弹栈
q=road_weight.top();//取栈里的首权值
road_weight.pop();
cout<<"第"<<i++<<"步为: "<<"顶点"<<p<<"-->到顶点"<<e<<" 长度为: "<<q<<endl;
}
}
cout<<"最短路径总长度为："<<dist[w]<<endl;//输出最短路径长度
}
template<class t,class e>
//graphlnk是一个带权有向图.数据成员e dist[v][j],
//0≤j<n, 是当前求到的从顶点v到 j的最短路 径长度,
//int path[v][j],0≤j<n, 存放求到的最短路径
void graphlnk<t,e>::dijkstra (int v )//dijkstra算法，求得图任意两点间的 最短路径
{ int k;//变量k
bool *s = new bool[this->numvertices];//并查集s，标记顶点是否已经在最短路径的顶点集里
this->path=new int [this->numvertices];//路径数组(跳跃式，要用回溯才能找出整个完整的路径)
this->dist= new int [this->numvertices];//源点v到任意顶点vi的最短路径数组，
for(int i = 0 ; i < this->numvertices;i++)//初始化
{
s[i]=false;//把所有的顶点都标记为:未在最短路径顶点集
if(this->getweight(v,i)!=maxweight)//如果有v和vi间如果有权值的话，那么，就是说，这两点是连通的。
// 既然两点是连通的，那么，这个路径就有可能是最短的。
this->dist[i]=this->getweight(v,i);
else //否则？就是没有连通咯，就用maxweight赋值给他，即：如果dist[i]==maxweight那么 就判定为两点是不连通的
dist[i]=maxweight;
if(this->dist[i]<maxweight||v==i)//如果有边连通，或者i==v
this->path[i]=v;//就让i这个顶点的前驱 是v (如果v==i 就让自己指向自己)
else
path[i]=-1;// 否则vi和 v 没有路，即两点间不连通
}
dist[v]=0;//首先，规定，v->v 即自己到自己的距离是0
s[v]=true;//将开始顶点v放入并查集数组中
int min;//最小路径的一个值
for(int i = 1; i <this->numvertices;i++)
{
min = maxweight;//首先要让这个最小值足够大，然后后面的那些路径权值才会比这个值小然后把它替换为真正的"最小值"
for(int j=0;j<this->numvertices;j++)
if(!s[j]&&dist[j]<min)//如果这个顶点没有在最小路径的顶点集里面，则判定是否连通
//如果连通的话，就从这些 连通的顶点间找到一组最小的连通 顶点。
{
k=j;
min=dist[j];
}
s[k]=true;//找一个：若在原来路径上 添加一个顶点，首先，这个顶点在最短路径顶点集和之外， 其次，这个顶点沿着其余顶点回到开始顶点路径最短
for(int w = 0 ; w <this->numvertices;w++)
//从这个新加入的顶点vnew出发，不断的去找和它相连接的顶点vi(i取任意正整数，即顶点可能不知有一个，可能是多个)
//然后看v到vi的路径短一点还是,v到vnew再到vi,如果是v到vnew 再到vi 比 直接从v到vi更短的话，那么就替换 v到vw的最小距离dist[w]
//并且规定w的前驱顶点为k ,即:path[w]=k; (此时w还没有在最短路径顶点集合里面)
//由此我们可以知道：既然每加入一个 顶点到 最短路径顶点集里面，都会执行这段代码。
//然后 都会从刚加入的那个顶点去 找遍所有 和它关联的顶点，所以，如果说这个加入的顶点如果 和目的顶点x相连，那么加入这个顶点后
// 执行下面的代码，就可以求出当前从始顶点到目的顶点x的最短路径,为什么是当前？因为这个最小是当前最小的，因为还有其他顶点未加入顶点集
//即有可能从 v出发 经过某个 未加入 最短路径顶点集合里的顶点 再到x 的路径大小 比 从v到原先那个加入 最短路径顶点集合里的顶点 再到x 的路径要小
//所以，下面的代码每次执行都会求得 一个临时的最短路径，如果顶点都加入完了，那么，自然是最短路径了
if(!s[w]&&dist[w]>(dist[k]+this->getweight(k,w))&&this->getweight(k,w)!=-1)
{
dist[w]=dist[k]+this->getweight(k,w);//
path[w]=k;//让w顶点的前驱是k
}
}
delete []s ;//删除标记数组
//输出代码可以在函数体里，也可以 加一个print函数 在函数体外
// cout<<"始顶点 "<<v<<" 到终顶点 "<<w<<" 的最短路径为：终顶点 "<< w;
// int current=w, previous;
// while( current!=v )
// {
// previous=path[current];
// cout<<"路径"<<path[current];
// cout<<"最小距离"<<dist[current];
// cout<<" <-权值[ "<<getweight(previous,current)<<" ]-顶点 "<<previous;
// current=previous;
// }
// cout<<"。最短路径总长度为："<<dist[w]<<endl;
}
template<class t, class e>
void graphlnk<t,e>::connected_component()//分别输出连通分量 和输出有向图中连通分量的个数
{ int connected_component_numbers=0;
bool visited[this->numvertices];
for(int i = 0 ; i <this->numvertices;i++)
visited[i]=false;//初始化这个visited 数组
for(int i =0; i < this->numvertices;i++)
{
if(!visited[i])//如果这个结点没有被访问过
{
cout<<"从"<<this->getvalue(i)<<"开始的连通分量为:";
this->dfs(i,visited);
cout<<endl;
connected_component_numbers+=1;
}
}
if(this->direction==true)
cout<<"此有向图的连通分量为:"<<connected_component_numbers<<endl;
else
cout<<"此无向图的连通分量为:"<<connected_component_numbers<<endl;
delete [] visited;//结束后删除数组
}
//从名为 v 的顶点出发广度优先遍历
template <class t, class e>
void graphlnk<t,e>::bfs(const t& v)
{ int i, w;
//创建访问标记数组
bool* visited = new bool[this->numvertices];
//对图中所有顶点初始化访问数组visited
for (i = 0; i < this->numvertices; i++)
visited[i] = false; //初始化为都未访问过
int loc = getvertexpos (v); //取名为 v 的顶点序号
if(loc == -1) //名为 v 的顶点未找到
cout<<"顶点 "<<v<<"没有找到，广度优先遍历失败。";
else
{
cout << getvalue (loc) << ' '; //访问顶点 v
visited[loc] = true; //标记顶点 v 已访问过
//顶点 v 进队列, 实现分层访问
queue<int> q;
q.push(loc); //访问过的顶点进队列
while (!q.empty() ) //循环, 访问所有结点
{ loc = q.front();//记录当前队列第一个顶点的值
q.pop(); // 然后记录完让它出队列
w = getfirstneighbor (loc); //取它的第一个邻接顶点
while (w != -1) //当邻接顶点w存在
{ if (!visited[w]) //如果未访问过
{ cout << getvalue (w) << ' ';//访问它然后输出它
visited[w] = true; //标记此顶点已经访问过
q.push(w); //顶点w进队列
}
w = getnextneighbor (loc, w); //取下一个邻接顶点
}
} //外层循环，判队列空否
}
delete [] visited;
}
template<class t , class e >
void graphlnk<t,e>::dfs(const t &v)
{
int sign;
bool *visited = new bool[this->numvertices];
for(int i = 0; i <this->numvertices;i++)
{
visited[i]=false;//初始化都为为访问过
}
sign=this->getvertexpos(v);
if(sign==-1)
cout<<"顶点"<<v<<"不存在"<<"深度优先遍历失败"<<endl;
else //否则为存在
dfs(sign,visited);
delete[] visited; //深度优先遍历完成的话，就删除这个数组
}
template<class t,class e>
void graphlnk<t,e>::dfs(int v , bool visited[])
{
cout<<this->getvalue(v)<<" ";
visited[v]=true;
int w = this->getfirstneighbor(v);
while(w!=-1)
{
if(!visited[w])//如果没有访问过为真
dfs(w,visited);
w=this->getnextneighbor(v,w);//否则回退 然后继续搜索
}
}
template<class t,class e>
bool graphlnk<t,e>::removeedge (int v1, int v2)//删除边这个比较简单
{
if(v1<0||v2<0||v1>this->numvertices||v2>this->numvertices)//这种情况就是不符合，不符合就返回false
return false ;
else //否则为符合的
{
edge_vertices<t,e> *temp;//这是一个中间变量
temp=this->nodetable[v1].next;//让它先等于顶点表个的下一个
while(temp)
{
if(temp->dest==v2)//如果一开始就是等于要删除的那个顶点的话(可能会有误解哦，这里不是删除边么，怎么删除顶点？)
//因为删除末顶点的话，就会少掉一条边
{
if(temp->link==null)//如果这条链只有这个待删除的顶点
{
this->nodetable[v1].next=null;//让顶点表的那个顶点的下一个顶点指向空
delete temp; //删除这个顶点
break;//跳出循环
}
else{ //如果不为空的话
this->nodetable[v1].next = temp->link;//让顶点表的下一个顶点指向 待删除 目标顶点的下一个
delete temp;//删除结点
break;
}
} if(temp)//防止内存访问出错
if(temp->link->dest ==v2)//不是第一个顶点是要删除的顶点 这个if 语句记作 aaaaa
{ edge_vertices<t,e> *temp2;//定义一个中间变量temp2
temp2=temp->link;//让temp 2指向 待删除 目标定点
temp->link=temp->link->link;//利用temp 断开 目标定点 与 子链的连接
delete temp2;//删除目标顶点
break;//跳出循环
} if(temp)//防止内存访问出错
temp=temp->link;//根据这条语句，会回到刚才 aaaaa 那个 if语句
}
//要考虑有向图和无向图哦
if(this->direction==false)//如果是无向图的话
{
temp=this->nodetable[v2].next;
while(temp)
{ //此段代码与上面的逻辑完全相同，不再赘述
if(temp->dest==v1)
{
if(temp->link==null)
{
this->nodetable[v2].next=null;
delete temp;
break;
}
else{
this->nodetable[v2].next = temp->link;
delete temp;
break;
}
}
if(temp)
if(temp->link->dest ==v1)
{ edge_vertices<t,e> *temp2;
temp2=temp->link;
temp->link=temp->link->link;
delete temp2;
break;
} if(temp)
temp=temp->link;
}
}
}
this->numedges--;//记得删完 边数要 -1;
return true;//删除成功返回true
}
template<class t , class e >
bool graphlnk<t,e>::removevertex (int v) //删除序号为 v 的顶点
{
if(v<0||v>=this->numvertices)//如果下标不符合规定
return false;
else //否则为符合
{
int del_vex_num=v;//记录这个删除的下标
if(v!=this->numvertices-1)//如果不是删除最后一个顶点的话
this->nodetable[v]=this->nodetable[--this->numvertices];//就用最后一个顶点顶的那条"链"替代这个待删除顶点的"链"
//如果删除的是最后一个顶点的话，自然就没有影响了
else
{
this->numvertices--;
int end_edg=0;//因为如果直接删掉这个点的话，那么这个点关联的边也要减掉
edge_vertices<t,e> *p;
p=this->nodetable[v].next;
while(p)
{
if(p)
{ end_edg++;//如果有一个顶点，且不为空的话，那么涉及的边数就+1
}
p=p->link;
}
this->numedges-=end_edg;
}
for(int i= 0 ; i < this->numvertices;i++)//此时的numvertices已经-1 ，然后对这所有的链进行操作，如果有将要删除顶点与这个顶点相连，则删除
{ edge_vertices<t,e> *temp;
temp=this->nodetable[i].next;
//第一种情况：第一个连接的 顶点就是 将要删除的那个顶点
//这种情况很好做
if(temp->dest ==v)
{
if(temp->link==null)//如果这条链只有一个结点，然后第一个结点恰好是这个将要删除的顶点的话
{
this->nodetable[i].next=null;//这样的话，直接删掉它
this->numedges--;
}
else //否则
{
this->nodetable[i].next=temp->link;
delete temp;//删除临时的指针变量
this->numedges--;
}
}
else //第二种情况，就需要循环了，因为每一个顶点最多只有一个 将要删除的那个顶点的下标
{//第一个结点的dest!=v
while(temp)
{
if(temp->link)
{
if(temp->link->dest==v)//第一个的下一个顶点刚好是 这个dest 的话
{
edge_vertices<t,e> *temp2;
temp2=temp->link;//中间变量temp2;
temp->link=temp->link->link;//断开这个将要删除的顶点
delete temp2;//删除刚才的中间变量//
this->numedges--;
break;
}
}
temp=temp->link;//这个最终会变成null,最后跳出循环;
}
}
}
if(v!=this->numvertices)//如果这个待删除的下标不等于 最后那个顶点的话 ，因为顶点 调动 位置，所以需要改变 链中顶点下标名字
for(int i = 0 ; i < this->numvertices;i++)
{ edge_vertices<t,e> *temp;
temp=this->nodetable[i].next;
while(temp)
{
if(temp)
if(temp->dest==this->numvertices)//就是说，最后的那个顶点要去前面 替换掉 刚才删除的那个顶点的位置 ，因此，下标也要改
{
temp->dest=v;// 循环遍历 出最后顶点的dest 然后用v 替换
break;
}
temp=temp->link;//移动
}
}
}//第一个else 的右括号
return true;//删除顶点成功
}
template<class t , class e>
e graphlnk<t,e>::getweight (int v1, int v2)//获得两个点之间的权值
{
if(v1<this->numvertices&&v2<this->numvertices&&v1!=v2)
{
// string a = this->nodetable[v2].data;
edge_vertices<t,e> *temp;
temp=this->nodetable[v1].next;//从v1这条链找一个点开始
while(temp)//然后循环，直到找到v2
{
if(temp->dest==v2)//找到了直接返回它的权值
return temp->cost;
else
temp=temp->link; //没找到，移动
}
return maxweight;
}
}
template<class t , class e >
bool graphlnk<t,e>::insertvertex (const t& vertex)//插入顶点 ，插在之前定义的那个顶点表那里
{
if(this->numvertices<this->maxvertices)//如果图当前的顶点数小于 允许插入的最大顶点数，则可以插入
{
this->nodetable[this->numvertices++].data=vertex;
}
}
template<typename t, typename e>
bool graphlnk<t,e>::insertedge(t in, t out, e cost)//插入边
{ int v1= getvertexpos(in); //这里还是直接是输入定点名，用函数找这个顶点的下标
int v2=getvertexpos(out);
if(v1>-1 && v1<this->numvertices && v2>-1 && v2 < this->numvertices )//这两个下标都在顶点表里
{ //将新边的权值插入边邻接矩阵的第v1行,v2列,利用头插法
edge_vertices<t,e> *temp =new edge_vertices<t,e>; //生成一个边结点。
temp->dest=v2;// 记录这个点的值
temp->link=this->nodetable[v1].next;//将它插在 v1 这个顶点的这条链里 ，这里采用头插法 (temp 街上nodetable[v1]的后面 一大串(当然一开始为空))
//比如这一大串为abcde 然后temp 接上去就为 temp->abcde;
if(this->withcost==true)//如果需要记录权值
temp->cost=cost;// 记录
this->nodetable[v1].next =temp;// 吧temp接上去 head ->temp->abcde;
if(this->direction==false)//如果是无向图的话，还要从v2那条链 接上 v1
{
edge_vertices<t,e> *temp2=new edge_vertices<t,e> ;
temp2->dest=v1;
temp2->link=this->nodetable[v2].next;
if(this->withcost==true)
temp2->cost=cost;//同样的是采用头插法，不再一一赘述
this->nodetable[v2].next=temp2;
}
this->numedges++;
return true;
}
else return false; //插入新边失败(不满足if 语句)
}
//构造函数建立邻接表
template <class t, class e>
graphlnk<t, e>::graphlnk (int sz,bool direct, bool cost):graph<t,e>(sz, direct, cost)
{ //创建源点表数组
nodetable = new vertex<t, e>[this->maxvertices];//分10个vertex结点大小 的指针 数组
if (nodetable == null)
{
cerr << "内存分配出错！" << endl; exit(1);
}
for (int i = 0; i < this->maxvertices; i++)
nodetable[i].next= null;//对nodetable的指针进行初始化
}
//析构函数：删除一个邻接表
template <class t, class e>
graphlnk<t, e>::~graphlnk()
{
for (int vertex = 0; vertex < this->numvertices; vertex++ ){
//current指向源点vertex边链表的第1个邻接点
edge_vertices<t, e> * current = nodetable[vertex].next;
while (current != null) {//邻接点存在
nodetable[vertex].next = current->link; //脱链
delete current; //释放边链表的第1个邻接点
// current重新指向边链表的第1个邻接点
current = nodetable[vertex].next;
}
}
delete []nodetable; //删除源点表数组
}
//返回序号为 v 的源点第1个邻接点的序号(从0开始),
//若未找到邻接点, 则返回-1
template <class t, class e>
int graphlnk<t, e>::getfirstneighbor (int v)
{ if (v != -1) //源点v存在
{ //current指向源点v的边链表第1个邻接点
edge_vertices<t, e>* current = nodetable[v].next;
if (current != null)//顶点v的第1个邻接点存在
//返回第1个邻接点的序号
return current ->dest;
}
return -1; //不存在第1个邻接点，返回-1
}
//返回源点v和邻接点w的下1个邻接点的序号，
//若未找到下1个邻接点, 则返回-1
template <class t, class e>
int graphlnk<t, e>::getnextneighbor (int v, int w)
{ if (v != -1) { //源顶点 v 存在
edge_vertices<t, e>* current = nodetable[v].next;//终顶点current
while (current != null && current->dest != w)
current = current->link; //先找到终顶点 w
if (current != null && current->link != null)
//返回w的下1个邻接顶点序号
return current->link->dest;
}
return -1; //未找到下1个邻接顶点，返回-1
}
template <class t, class e>
void graphlnk<t,e>::enter()
{ int count,vertexs,edges;
t e1,e2;
cout<<"图*有多少个顶点？";
cin>>vertexs;
cout<<"输入图* "<<vertexs<<" 个顶点名：";
//输入图中全部顶点名
for(count=0;count<vertexs;count++)
{ cin>>e1;
insertvertex(e1);
}
e weight;
char answer;
cout<<"图形的边有方向吗(y/n)?";
cin>>answer;
if(answer=='y' || answer=='y')
this->direction=true;
else
this->direction=false;
cout<<"图中的边带权吗(y/n)?";
cin>>answer;
if(answer=='y' || answer=='y')
this->withcost=true;
else
this->withcost=false;
cout<<"图*有多少条边？";
cin>>edges;
count=0;
while(count<edges)
{
cout<<"输入第 "<<count+1<<" 条边的2个顶点名和权值：";
cin>>e1>>e2>>weight;
if(insertedge(e1,e2,weight))
count++;
else
cout<<"顶点名有误，重新输入这条边！"<<endl;
}
}
// 输出图中所有顶点和边的信息
template <class t, class e>
void graphlnk<t, e>::print(void)
{ int row,column;
e weight;
cout<<"图*有 "<<this->numvertices<<" 个顶点和 "<<this->numedges<<" 条边："<<endl;
for(row=0;row<this->numvertices;row++)
{
//按行号取出序号为row的顶点名并输出
cout<<"序号"<<row<<"源点"<<"["<<getvalue(row)<<"]"<<"->";
edge_vertices<t, e> *temp;
temp=this->nodetable[row].next;
if(temp)//可能它的下一个顶点直接就是空
{
while(temp->link)
{
cout<<"["<<"邻接点"<<temp->dest<<"]";
if(this->withcost)
cout<<"["<<"权值"<<temp->cost<<"]";
cout<<"[-]->" ;
temp=temp->link;
}
cout<<"["<<"邻接点"<<temp->dest<<"]";
if(this->withcost)
cout<<"["<<"权值"<<temp->cost<<"]";
cout<<"[^]" ;
cout<<endl;
}
else
cout<<"[^]"<<endl;
}
}
int main()
{
graphlnk<string,double> graph;
graph.enter();
graph.print();
// string del;
// cout<<"请输入你想要删除的一个顶点"<<endl;
// cin>>del;
// int index= graph.getvertexpos(del);
// if(graph.removevertex (index))
// cout<<"删除成功"<<endl;
// else
// cout<<"删除失败";
// graph.print();
// cout<<"请输入你想要删除那条边的两个顶点"<<endl;
// string one ,two;
// cin>>one>>two;
// int num_one,num_two;
// num_one=graph.getvertexpos(one);
// num_two=graph.getvertexpos(two);
// if(graph.removeedge(num_one,num_two))
// cout<<"删除成功"<<endl;
// else
// cout<<"删除失败"<<endl;
// graph.print();
//cout<<"请输入一个顶点来进行深度优先遍历"<<endl;
// string dfs;
// cin>>dfs;
// graph.dfs(dfs);
// cout<<endl;
//cout<<"请输入一个顶点来进行广度优先遍历"<<endl;
//string bfs;
//cin>>bfs;
//graph.bfs(bfs);
//cout<<endl;
//graph.connected_component();
string a,b;
cout<<"输入求最短路径的始顶点：";cin>>a;
int v = graph.getvertexpos(a);
cout<<"输入求最短路径的终顶点：";cin>>b;
int w = graph.getvertexpos(b);
graph.dijkstra(v);
graph.print(v,w);
//system("pause");
}
运行结果如下:
以上就是c++ dijkstra算法之求图中任意两顶点的最短路径的详细内容，更多关于c++ 的资料请关注其它相关文章！
上一篇： Zabbix分布式监控系统