首页 > 代码库 > 最短路径
最短路径
本文为原创：转载请注明来至http://blog.csdn.net/j903829182/article/details/37989633
/*
最短路径：
1.在一个图中，若从一个顶点到另一个顶点存在着路径，则定义路径长度为一条路径上所有经过的边的数目。
图中从一个顶点到另一个顶点可能存在多条路径，我们把路径长度最短的那条路径叫作最短路径，其路径长度叫做最短路径长度或最短距离
在一个带权图中，若从一个顶点到另一个存在着一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个顶点
到另一个顶点可能存在着多条路径，我们把带权路径长度值最小的那条路径也叫作最短路径，其带权路径长度叫作最短路径长度或最短距离。
2.狄克斯特拉算法：
对于有向带权图中从一个确定顶点（称为源点）到其余各顶点的最短路径问题，狄克斯特拉（Dijkastra）提出了一个按路径长度递增的顺序逐步产生最短路径
的构造方法。
狄克斯特拉算法思想：设置两个顶点集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合
S中只包含了源点，设为v0，然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余
顶点的当前最短路径长度值，集合T中各顶点的新的当前最短路径值为原来的当前路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T
中的顶点全部加入到集合S中为止。
*/
#include<stdio.h>
#include<malloc.h>
#define MaxSize 10 //定义元素的大小
typedef char DataType; //定义一个类型
#define MaxVertices 10 //定义顶点的最大值
#define MaxWeight 10000 //定义无穷大的具体值
typedef char VerT;
typedef struct{ //定义一个结构体
DataType list[MaxSize];
int size; //结构体元素的大小
}SeqList; //结构体的对象
typedef struct{
SeqList Vertices;//存放顶点的顺序表
int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵
int numOfEdges;//边的条数
}AdjMGraph;
typedef struct{
int row;//行下标
int col;//列下标
int weight;//权值
}RowColWeight;//边信息结构体
typedef struct{
VerT vertex;//保存最小生成树每条边的弧头顶点数据
int weight;//保存最小生成树的相应边的权值
}MinSpanTree;
//初始化
void initiate(SeqList *L){
L->size=0;//定义初始化元素个数
}
//求当前元素的个数
int getLength(SeqList L){
return L.size;//返回长度
}
//插入数据元素
int insertData(SeqList *L,int i,DataType x){
//在顺序表L的第i(0<=i<=size)个位置前插入数据元素x
//插入成功返回1，出人失败返回0
int j;
if(L->size>=MaxSize){
printf("顺序表已满，无法插入!!\n");
return 0;
}else if(i<0||i>L->size){
printf("插入的位置不合法，不在指定的范围，参数i不合法!\n");
return 0;
}else{
//从后向前一致移动数据，为插入做准备
for(j=L->size;j>i;j--){
L->list[j]=L->list[j-1];
}
L->list[i]=x;
L->size++;
return 1;
}
}
//删除数据
int deleteData(SeqList *L,int i,DataType *x){
//删除顺序表中位置为i的数据i>=0&&i<=size-1，把数据保存到x中
//删除成功返回1，否则返回0
int j;
if(L->size<=0){
printf("顺序表已空无数据元素可删!\n");
return 0;
}else if(i<0||i>L->size-1){
printf("参数i不合法，不能删除!\n");
return 0;
}else{
*x=L->list[i];
for(j=i+1;j<=L->size-1;j++){//从前往后一次前移
L->list[j-1]=L->list[j];
}
L->size--;//数据元素减一
return 1;
}
}
//取出数据元素
int getData(SeqList L,int i,DataType *x){
if(i<0||i>L.size-1){
printf("参数i不合法，不能删除!\n");
return 0;
}else{
*x=L.list[i];
return 1;
}
}
//初始化有n个顶点的顺序表和邻接矩阵
void InitiateG(AdjMGraph *g,int n){
//初始化
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j){
g->edge[i][j]=0;
}else{
g->edge[i][j]=MaxWeight;//MaxWeight表示无穷大
}
}
}
g->numOfEdges=0;//边的条数置为0
initiate(&g->Vertices);//顺序表初始化
}
//插入顶点
void InsertVertex(AdjMGraph *g,DataType vertex){
//在图G中插入顶点vertex
insertData(&g->Vertices,g->Vertices.size,vertex);//顺序表尾插入
}
//插入边
void InsertEdge(AdjMGraph *g,int v1,int v2,int weight){
//在图中插入边<v1,v2>,边<v1,v2>的权为weight
if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){
printf("参数v1或v2越界出错!!!\n");
return ;
}
g->edge[v1][v2]=weight;
g->numOfEdges++;
}
//删除边
void DeleteEdge(AdjMGraph *g,int v1,int v2){
//在G图中删除边<v1,v2>
if(v1<0||v1>=g->Vertices.size||v2<0||v2>=g->Vertices.size){
printf("参数v1或v2越界出错!!!\n");
return ;
}
if(g->edge[v1][v2]==MaxWeight||v1==v2){
printf("该边不存在!!!\n");
return;
}
g->edge[v1][v2]=MaxWeight;
g->numOfEdges--;
}
//取第一个邻接顶点
int GetFirstVex(AdjMGraph g,int v){
//在图G中寻找序号为v的顶点的第一个邻接顶点
//如果这样的顶点存在，则返回该邻接顶点的序号，否则返回-1
int col;
if(v<0||v>=g.Vertices.size){
printf("参数v1越界出错!!!\n");
return -1;
}
for(col=0;col<g.Vertices.size;col++){
if(g.edge[v][col]>0&&g.edge[v][col]<MaxWeight){
return col;
}
}
return -1;
}
//取下一个邻接顶点
int GetNextVex(AdjMGraph g,int v1,int v2){
//在图中寻找v1顶点的邻接顶点v2的下一个邻接顶点
//如果这样的邻接顶点存在，则返回该邻接顶点的序号；否则返回-1
//v1和v2都是相应的顶点的序号
int col;
if(v1<0||v1>g.Vertices.size||v2<0||v2>=g.Vertices.size){
printf("参数v1或v2越界出错!!!\n");
return -1;
}
for(col=v2+1;col<g.Vertices.size;col++){
if(g.edge[v1][col]>0&&g.edge[v1][col]<MaxWeight){
return col;
}
}
return -1;
}
void CreatGraph(AdjMGraph *g,DataType V[],int n,RowColWeight E[],int e){
//在图中插入n个顶点信息V和e条边信息E
int i,k;
InitiateG(g,n);//d顶点顺序表初始化
for(i=0;i<n;i++){
InsertVertex(g,V[i]);//插入顶点
}
for(k=0;k<e;k++){
InsertEdge(g,E[k].row,E[k].col,E[k].weight);//插入边
}
}
//普里姆函数设计
//参数g为邻接矩阵存储结构的图
//closeVertex为通过函数得到的最小生成树的顶点和相应顶点边的权值数据
void Prim(AdjMGraph g,MinSpanTree closeVertex[]){
//用普里姆算法建立带权图G的最小生成树closeVertex
VerT x;
int n=g.Vertices.size,minCost;
int *lowCost=(int *)malloc(sizeof(int)*n);//保存集合U中顶点ui与集合V-U中顶点vj的所有边中当前具有最小权值的边(u,v)
int i,j,k;
for(i=1;i<n;i++){//初始化
//lowCost的初始值为邻接矩阵数组中第0行的值
lowCost[i]=g.edge[0][i];//存放了从集合U中顶点0到集合V-U中各个顶点的权值
}
//从顶点0出发构造最小生成树
getData(g.Vertices,0,&x);//取顶点0
closeVertex[0].vertex=x;//保存顶点
lowCost[0]=-1;//标记顶点
for(i=1;i<n;i++){
//寻找当前最小权值的边对应的弧头顶点k
minCost=MaxWeight;//MaxWeight为定义的最大值
for(j=1;j<n;j++){
if(lowCost[j]<minCost&&lowCost[j]>0){
minCost=lowCost[j];
k=j;
}
}
getData(g.Vertices,k,&x);//取弧头顶点k
closeVertex[i].vertex=x;//保存弧头顶点k的数据
closeVertex[i].weight=minCost;//保存相应的权值
lowCost[k]=-1;//标志顶点k
//根据加入集合U的顶点k修改lowCost中的数值
for(j=1;j<n;j++){
if(g.edge[k][j]<lowCost[j]){
lowCost[j]=g.edge[k][j];
}
}
}
}
//狄克斯特拉算法函数的设计
//函数共有4个参数,其中2个为输入参数，分别为带权图G和源点序号v0；两个为输出参数
//分别为distance[]和path[]，distance[]用来存放得到从源点v0到其余各顶点的最短距离数值
//path[]用来存放得到的从源点v0到其余各顶点的最短路径上到目标顶点的前一顶点的下标
void Dijkstra(AdjMGraph g,int v0,int distance[],int path[]){
//带权图G从下标v0顶点到其他顶点的最短距离distance和最短路径下标
int n=g.Vertices.size;
//s[i]=0表示顶点i在集合T中，s[i]=1表示顶点i已从集合T移到集合S中
int *s=(int *)malloc(sizeof(int)*n);
int minDis,i,j,u;
//初始化
for(i=0;i<n;i++){
distance[i]=g.edge[v0][i];
s[i]=0;
if(i!=v0&&distance[i]<MaxWeight){
path[i]=v0;
}else{
path[i]=-1;
}
}
s[v0]=1;//标志顶点v0已从集合T加入到集合S中
//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u
for(i=1;i<n;i++){
minDis=MaxWeight;
for(j=0;j<n;j++){
if(s[j]==0&&distance[j]<minDis){
u=j;
minDis=distance[j];
}
}
//当已不在存在路径时，算法结束。此语句对非连通图是必需的
if(minDis==MaxWeight){
return;
}
s[u]=1;//标志顶点u已经从集合T中加入到集合S中
//修改从v0到其他顶点的最短距离和最短路径
for(j=0;j<n;j++){
if(s[j]==0&&g.edge[u][j]<MaxWeight&&
distance[u]+g.edge[u][j]<distance[j]){
//顶点v0经顶点u到其他顶点的最短距离和最短路径
distance[j]=distance[u]+g.edge[u][j];
path[j]=u;
}
}
}
}
void main(){
/*
AdjMGraph g;
DataType a[]={'A','B','C','D','E','F','G'};
RowColWeight rcw[]={{0,1,50},{1,0,50},{0,2,60},{2,0,60},{1,3,65},
{3,1,65},{1,4,40},{4,1,40},{2,3,52},{3,2,52},{2,6,45},{6,2,45},
{3,4,50},{4,3,50},{3,5,30},{5,3,30},{3,6,42},{6,3,42},{6,2,45},
{4,5,70},{5,4,70}};
int n=7,e=20;
int i,j;
MinSpanTree closeVertex[7];//定义保存最小生成树的数组
CreatGraph(&g,a,n,rcw,e);//创建图
Prim(g,closeVertex);//调用Prim函数
//输出Prim函数得到最小生成树的顶点序列和权值
printf("初始顶点=%c\n",closeVertex[0].vertex);
for(i=1;i<n;i++){
printf("顶点=%c 边的权值=%d\n",closeVertex[i].vertex,closeVertex[i].weight);
}
*/
AdjMGraph g;
DataType a[]={'A','B','C','D','E','F'};
RowColWeight rcw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,15},
{2,5,7},{4,3,4},{5,3,10},{5,4,18}};
int i,n=6,e=9;
int distance[6],path[6];
CreatGraph(&g,a,n,rcw,e);//创建图
Dijkstra(g,0,distance,path);
printf("从顶点%c到其他各顶点的最短距离为：\n",g.Vertices.list[0]);
for(i=0;i<n;i++){
printf("到顶点%c的最短距离为%d\n",g.Vertices.list[i],distance[i]);
}
printf("\n从顶点%c到其他各顶点最短路径的前一顶点为:\n",g.Vertices.list[0]);
for(i=0;i<n;i++){
if(path[i]!=-1){
printf("到顶点%c的前一顶点为%c\n",
g.Vertices.list[i],g.Vertices.list[path[i]]);
}
}
}
最短路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。