|
Dijkstra算法是图中找任意两点中最短路径的一种经典算法。 重点的步骤总结如下： ①:算法采用了并查集 (之后都叫它为 最短路径顶点集 ):即每次都找离开始顶点距离最短的顶点，然后把该顶点加入最短路径顶点集中(已经加入最短路径顶点集里的那些顶点 下一次就会跳过它了，并且，在顶点集里 任意两个顶点间的距离 都已经是最短) ②:用来记录从源点(开始顶点) 到vi (0v1—>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
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const long long int maxWeight = RAND_MAX; //无穷大的值
const int DefaultVertices = 30; //最大顶点数不妨设为30
template
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
Graph::Graph (int sz , bool direct, bool cost)
{
sz = DefaultVertices, direct=false, cost=false;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
template //
class Edge_Vertices {
//边结点的类定义
public:
int dest; //边的邻接(终)点序号
E cost; //边上的权值
Edge_Vertices* link;//下一个连接顶点
Edge_Vertices (int num=0, Edge_Vertices* next=NULL, E weight=NULL) //构造函数
: dest (num), link (next), cost (weight) {
}
bool operator != (Edge_Vertices& R) const
{
return dest != R.dest; } //重载!=运算符,判边不等
};
template
class Vertex {
//顶点的类定义
public:
T data; //源顶点的名字(数据)
Edge_Vertices* next=NULL; //next指针用来连接顶点
};
//邻接表图的类定义继承图类
template
class Graphlnk : public Graph{
public:
void Enter (void); //输入图中顶点和边信息
void Print (void); //输出图中顶点和边信息
//源顶点表 (各边链表的源顶点)
Vertex* NodeTable;
int *path;
int *dist;
//返回名为vertex的顶点在图中的序号(从0开始)，
//若未找到，则返回-1
int getVertexPos (const T vertx) //找到目标顶点所在的序号 期中 vertx 参数为string 类型
{
for (int i = 0; i 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 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,
|