带权图最短路径的一种算法

摘 要：本文主要是，给出求带权图最短路径的一种算法，并通过图的邻接矩阵存储方式和C++语言实现.

【关键词】邻接矩阵 顶点 权值 最短路径

1 定义图（邻接矩阵）类

template

class Graph

{ private：

T *ver； //数组ver存贮图中各个顶点的数据

int **edge；//数组edge为图的邻接矩阵

int vers ，edges；//变量vers和edges分别存贮图的顶点个数和边个数

bool tag；//tag是个标记变量，若值为0表示是无向图，否则是有向图

boll *visit；//数组visit[i] 用于标记顶点i是否已被访问

int *path ，n ， distance；//数组path用于暂存所找出的当前路径，变量n暂存当前路径中的顶点个数，变量distance暂存当前路径的长度

int m；//变量m用于存贮找到的所有路径的条数

int *minpath ，minn ， mindistance；//数组minpath存贮要找的最短路径，变量minn存贮最短路径中的顶点个数，变量mindistance存贮最短路径的长度

void find（int v ， const int w）；//访问从顶点v到顶点w之间的所有路径，并找出其中最短的路径

public：

Graph（bool p ，T a[] ，int n ，int e）；//构造函数

void shortpath（ int v ，int w）；//求从顶点v到顶点w之间的最短路径

}；

构造函数Graph（p ，a ， n ， e）是通过数组a中的数据创建一个有n个顶点和e条边的图，若p值为0，则建立无向图，否则建立有向图。

template

Graph：： Graph（bool p ，T a[] ，int n ，int e）

{ tag=p； vers=n； edges=e；

int i， j ， k ， w；

//初始化

ver=new T[vers]； for（i=0；i

edge=new int*[vers]；

for（i=0；i

//建立图中的各个边

cout

for（k=0；k>i>>j>>w； edge[i][j]=w； if（tag==0）edge[j][i]=w；}

return；

}

2 寻找带权图的最短路径

算法的基本思想是：按照深度优先搜索的方法，在图中访问从一个顶点到另一个顶点之间的每一条路径，并从中找出最短的路径，若同时存在多条长度相同的最短路径，则选取其中顶点个数最少的一条。

（1）函数find（v ，w）是访问图中从顶点v到顶点w之间的所有路径，并从中找出最短的路径。

template

void Graph：：find（int v ， const int w）

{ path[n++]=v； visit[v]=1；//先将顶点v添加到当前路径path中，并置其访问标志为1

if（n>1）distance+=edge[path[n-2]][v]；//修改当前路径path的长度

if（path[n-1]==w）//找到一条从顶点v到顶点w之间的路径

{ if（mindistance>distance||（mindistance==distance&&minn>n））

{ mindistance=distance； minn=n； for（int i=0；i

m++；

}

else for（int i=0；i

n--； visit[v]=0；//再从当前路径path中删除顶点v，并将其访问标志重新置为0

if（n>0）distance-=edge[path[n-1]][v]； //修改当前路径path的长度

return；

}

（2）函数shortpath（ v ，w）是求图中从顶点v到顶点w之间的最短路径。

template

void Graph：：shortpath（int v ，int w）

{ if（v=vers||w=vers||v==w） return；

//先进行有关初始化

path=new int[vers]； minpath=new int[vers]；；visit=new bool[vers]；

int i，j； for（i=0；i

n=0； distance=0； minn=0； mindistance=0； m=0；

//开始求最短路径

find（v ，w）；

if（m==0）

cout

else

{ cout

for（i=0；i

cout

}

return ；

}

参考文献

[1]王红梅.数据结构（C++版）[M].清华大学出版社，2009.

[2]夏克俭.数据结构与算法[M].国防工业出版社，2000.

[3]严蔚敏.数据结构（C语言版）[M].清华大学出版社，2003.

[4]翁惠玉.数据结构与实现[M].高等教育出版社，2009.

作者简介

孙风庆（1963-），男，山东省定陶县人，副教授，大学学历，工学学士，主要研究方向是计算方法和数据结构。

作者单位

山东德州职业技术学院计算机系 山东省德州市 253034