首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 狄杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。
打开IDE
我们创建一个工程
类声名如下 #if !defined(AFX_GRAPH_H__EDF8E290_EF85_4726_851D_F684E5602E43__INCLUDED_)#define AFX_GRAPH_H__EDF8E290_EF85_4726_851D_F684E5602E43__INCLUDED_#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000//图的相关数据类型的定义graph.h//最多顶点数const int MaxV=10;//最大权值const int MaxValue=99;//定义邻接表中的边结点类型struct edgenode { int adjvex; //邻接点域 int weight; //权值域 edgenode* next;//指向下一个边结点的链域};//定义邻接表类型typedef edgenode** adjlist;//邻接矩阵类定义class AdjMatrix{private:char g[MaxV];//顶点信息数组int size;//当前顶点数int GA[MaxV][MaxV];//定义邻接矩阵GAint numE;//当前边数public: //构造函数,初始化图的邻接矩阵 AdjMatrix(int n,int k2); //判断图空否 bool GraphEmpty() {return size==0;} //取当前顶点数 int NumV() {return size;} //取当前边数 int NumEdges() {return numE;} //取顶点i的值 char GetValue(const int i); //取弧 的权 int GetWeight(const int v1,const int v2); //在位置pos处插入顶点V void InsertV(const char &V,int pos); //插入弧 ,权为weight void InsertEdge(const int v1,const int v2,int weight); //删除顶点i与顶点i相关的所有边 char DeleteVE(const int i); //删除弧 void DeleteEdge(const int v1,const int v2); //建立图的邻接矩阵 void CreateMatrix(int n, int k1,int k2); //k1为0则无向否则为有向,k2为0则无权否则为有权 //从初始点vi出发深度优先搜索由邻接矩阵表示的图 void dfsMatrix(bool*& visited,int i,int n,int k2); //从初始点vi出发广度优先搜索由邻接矩阵表示的图 void bfsMatrix(bool*& visited,int i,int n,int k2); //由图的邻接矩阵得到图的邻接表 void graphChange(adjlist &GL,int n,int k2); //检查输入的边序号是否越界,若越界则重输 void Check(int n,int& i,int& j); //由图的邻接矩阵建立图 void Creatgraph(int n,int k2); //对非连通图进行深度优先搜索 void dfsMatrix(int n,int k2); //对非连通图进行广度优先搜索 void bfsMatrix(int n,int k2);};#endif // !defined(AFX_GRAPH_H__EDF8E290_EF85_4726_851D_F684E5602E43__INCLUDED_) 类实现如下 #include "stdafx.h"#include "graph.h"//图的相关运算的实现graph.cpp#include"graph.h"//构造函数,初始化图的邻接矩阵AdjMatrix::AdjMatrix(int n,int k2){int i,j; if(k2==0){//初始化无(有)向无权图 for(i=0;i >e; if(k1==0 && k2==0) { //建立无向无权图 cout<<"输入"< <<"条无向无权边的起点和终点序号!"< >i>>j; Check(n,i,j); GA[i][j]=GA[j][i]=1;} } else if(k1==0 && k2!=0) { //建立无向有权图 cout<<"输入"< <<"条无向带权边的起点和终点序号及权值!"< >i>>j>>w; Check(n,i,j); GA[i][j]=GA[j][i]=w;} } else if(k1!=0 && k2==0) { //建立有向无权图 cout<<"输入"< <<"条有向无权边的起点和终点序号!"< >i>>j; Check(n,i,j); GA[i][j]=1;} } else if(k1!=0 && k2!=0) { //建立有向有权图 cout<<"输入"< <<"条有向有权边的起点和终点序号及权值!"< >i>>j>>w; Check(n,i,j); GA[i][j]=w;}} numE=e; cout<<"创建后的邻接矩阵:\n"; for(i=0;i =n||j<0||j>=n) cout<<"输入有误,请重输!"; else return; cin>>i>>j; }}//由图的邻接矩阵得到图的邻接表void AdjMatrix::graphChange(adjlist &GL,int n,int k2){int i,j; if(k2==0) {for(i=0;i adjvex=j; p->next=GL[i];GL[i]=p; cout<<'('< <<','< adjvex<<") ";} cout< adjvex=j;p->weight=GA[i][j]; p->next=GL[i];GL[i]=p; cout<<'('< <<','< adjvex<<','< weight<<") ";} cout< size) {cerr<<"参数i越界!\n";exit(1);} return g[i];}//取弧 的权int AdjMatrix::GetWeight(const int v1,const int v2){if(v1<0||v1>size||v2<0||v2>size) {cerr<<"参数v1或v2越界!\n";exit(1);} return GA[v1][v2]; }//在位置pos处插入顶点Vvoid AdjMatrix::InsertV(const char &V,int pos){int i; if(size==MaxV) {cerr<<"表已满,无法插入!\n";exit(1);} if(pos<0||pos>size) {cerr<<"参数pos越界!\n";exit(1);} for(i=size;i>pos;i--) g[i]=g[i-1]; g[pos]=V; size++; }//插入弧 ,权为weightvoid AdjMatrix::InsertEdge(const int v1,const int v2,int weight){if(v1<0||v1>size||v2<0||v2>size) {cerr<<"参数v1或v2越界!\n";exit(1);} GA[v1][v2]=weight; numE++; }//删除顶点v与顶点v相关的所有边char AdjMatrix::DeleteVE(const int v){for(int i=0;i 0&&GA[i][j] size-1) {cerr<<"参数v越界!\n";exit(1);} char temp=g[v]; for(int i=v;i void AdjMatrix::DeleteEdge(const int v1,const int v2){if(v1<0||v1>size||v2<0||v2>size||v1==v2) {cerr<<"参数v1或v2出错!\n";exit(1);} GA[v1][v2]=MaxValue; numE--;}//对非连通图进行深度优先搜索void AdjMatrix::dfsMatrix(int n,int k2){bool *vis=new bool[NumV()]; for(int i=0;i 代码调用如下 #include "stdafx.h"#include "graph.h"//网G从下标v0到其他顶点的最短距离dist和最短路径下标pathvoid PShortPath(AdjMatrix &G,int v0,int dist[],int path[]){int n=G.NumV();int *s=new int[n];int mindis,i,j,u;for(i=0;i }效果如下
代码下载如下