Question

单源最短路径_单源结点最短路径

Answer 1

单源结点最短路径

一、题目

单源结点最短路径问题。

二、问题描述

求从有向图的某一结点出发到其余各结点的最短路径。

三、基本要求

（1） 有向图采用邻接矩阵表示。

（2） 单源结点的最短路径问题采用狄克斯特拉算法。

（3） 输出有向图中从源结点到其余各结点的最短路径和最短路径值。

四、测试数据

测试数据为如下图所示的有向带权图，以结点v1作为源结点，求从结点v1到其余各结点的最短路径和最短路径的长度值。

图 有向带权图

五、算法思想

1. 算法流程图

算法流程图

（2）算法分析

按已给有向图构造出图G 结构体，顺序表存储顶点信息，矩阵存储邻接矩阵信息，记录边的条数；选择v1为起始顶点，用狄克斯特拉算法求v1顶点到其他各个顶点的最短路径值和最短距离。

将所有的顶点分为S 、T 两类，S 用来存放已知最短路径的顶点。而T 存放未知最短路径的顶点。如果起始点（v1）到某个相邻顶点的最短距离已经求出，比如v1-v2的距离。那么就把v2归入S ，其余的不能直接算出最短距离的则要归入T 。

刚开始的S 只有起始点一个，随着算法的继续，首先将起始点相邻的点归入到S ，知道最后一个顶点归入S 。

六、模块划分

1. 创建图

（1）算法流程

创建图流程

（2）求得G 图结构如下图所示：

2. 求最短路径和最短距离

算法流程图

（1）求得最短距离矩阵如下

⎡0-1-1-1⎢01-1-1⎢

⎢02-1-1

path [6][6]=⎢

⎢0253⎢0253⎢

⎢025-1⎣

-1-1⎤

-1-1⎥⎥-1-1⎥

⎥

-1-1⎥4-1⎥

⎥

-1-1⎦⎥

（2）求得最短距离矩阵如下

distance [6]=[[1**********]]

七、数据结构

1. 结构体定义

（1）图的结构体定义

typedef struct {

SeqList Vertices; //存放顶点的顺序表 int edge[MaxVertices][MaxVertices]; //存放边的邻接矩阵 int numOfEdges; }AdjMGraph; （2）边信息结构体定义 typedef struct {

int row; int col;

int weight; }RowColWeight;

八、源程序

1. 子函数AdjMGraph.h

/**邻接矩阵存储存储结构下图操作的实现**/

#ifndef ADJMGRAPH_H_INCLUDED #define ADJMGRAPH_H_INCLUDED

#include "SeqList.h"

typedef struct {

SeqList Vertices; int edge[MaxVertices][MaxVertices]; int numOfEdges; }AdjMGraph;

/**初始化有n 个顶点的顶点顺序表和邻接矩阵**/

//边的条数 //图的结构体定义 //行下标 //列下标 //权值

//边信息结构体定义

//包含顺序表头文件 //存放顶点的顺序表 //存放边的邻接矩阵 //边的条数

//图的结构体定义

void Initiate(AdjMGraph *G, int n) {

int i,j;

for(i=0;i

for(j=0;j

if(i==j) G->edge[i][j]=0;

else G->edge[i][j]=MaxWeight; //MaxWeight 表示无穷大 }

G->numOfEdges=0; //边的条数置为0 ListInitiate(&G->Vertices); //顺序表初始化 }

/**在图中增加一个顶点**/

void InsertVertex(AdjMGraph *G, DataType vertex) //在图中插入顶点vertex {

ListInsert(&G->Vertices,G->Vertices.size,vertex); //顺序表尾插入 }

/**在图中增加一条有向边**/

void InsertEdge(AdjMGraph *G, int v1, int v2, int weight)

//在图G 中插入边，边的权为weight {

if(v1 = G->Vertices.size || 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 中删除边

if(v1 = G->Vertices.size || v2 = G->Vertices.size || v1 == v2 ) {

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 = G.Vertices.size) {

printf("参数v1越界！\n"); return -1; }

for(col = 0; col

if(G.edge[v][col]>0&&G.edge[v][col]

return -1; }

/**取下一个邻接顶点**/

int GetNextVex(AdjMGraph G,int v1, int v2)

//在图G 中寻找V1顶点的邻接顶点V2的下一个邻接顶点 {

int col;

if(v1 = G.Vertices.size || v2 = G.Vertices.size) {

printf("参数v1或v2越界出错！\n"); return -1; }

for(col=v2+1;col

if(G.edge[v1][col]>0&&G.edge[v1][col]

return -1; }

#endif // ADJMGRAPH_H_INCLUDED

2. 子函数AdjMGraphCreate.h

/**图的创建函数**/

#ifndef ADJMGRAPHCREATE_H_INCLUDED #define ADJMGRAPHCREATE_H_INCLUDED

typedef struct {

int row; //行下标 int col; //列下标 int weight; //权值

}RowColWeight; //边信息结构体定义

void CreatGraph(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e) //在图G 中出入n 个顶点信息V 和e 条边的信息E {

int i,k;

Initiate(G,n); //顶点顺序表初始化

for(i=0;i

InsertVertex(G,V[i]); //插入顶点

for(k=0;k

InsertEdge(G,E[k].row,E[k].col,E[k].weight); //插入边

}

#endif // ADJMGRAPHCREATE_H_INCLUDED

3. 子函数Dijkstra.h

#ifndef DIJKSTRA_H_INCLUDED #define DIJKSTRA_H_INCLUDED #define N 6

void Dijkstra(AdjMGraph G, int v1, int distance[], int path[][N])

//带权图G 从下标v1顶点到其他顶点的最短距离distance 和最短路径下标path {

int n=G.Vertices.size;

int *s=(int*)malloc(sizeof(int)*n); int minDis,i,j,u,k;

//初始化

for(i=0;i

path[i][0]=v1; for(j=1;j

for(i=0;i

distance[i]=G.edge[v1][i]; s[i]=0;

if(i!=v1&&distance[i]

//标记顶点v0已从集合T 加入到集合S 中 s[v1]=1;

//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u for(i=1;i

minDis=MaxWeight;

for(j=0;j

if(s[j]==0 && distance[j]

u=j;

minDis=distance[j]; }

//当已不存在路径时，算法结束。此句对非连通图是必需的 if(minDis==MaxWeight) return;

//标记顶点u 已从集合T 加入到集合S 中 s[u]=1;

//修改从v0到其他顶点的最短路径和最短距离 for(j=0;j

if(s[j]==0 && G.edge[u][j]

//顶点v0经顶点U 到其他顶点的最短距离和最短路径 distance[j]=distance[u]+G.edge[u][j]; for(k=0;path[u][k]!=-1;k++) {

path[j][k]=path[u][k]; }

path[j][k++]=j; path[j][k]=-1; } } } }

#endif // DIJKSTRA_H_INCLUDED

4. 子函数SeqList.h

#ifndef SeqList_H #define SeqList_H

typedef struct { DataType list[MaxSize]; // DataType这个在你用的时候可以去定义它的类型 int size; //指这个表的总长度

}SeqList; //定义抽象数据类型SeqList

void ListInitiate(SeqList *L) // 初始化顺序表L { L->size=0; // 定义初始元素个数 }

int ListLength(SeqList L)

{

return L.size;

}

int ListInsert(SeqList *L,int i,DataType x)

//在顺序表L 的位置i （0

{

int j;

if(L->size >= MaxSize)

{

printf("表已满无法插入！\n");

return 0;

}

else if(iL->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 ListDelete(SeqList *L,int i,DataType *x)

//删除顺序表L 中位置i 上的数据元素并保存到x 中

//插入成功返回1，否则返回0

{

int j;

if(L->size

{

printf("表已空无法插入！\n");

return 0;

}

else if(iL->size-1)

{

printf("参数i 不合法！\n");

return 0;

}

else

{

*x=L->list[i];

for(j=i+1;jsize-1;j++)

L->list[j-1]=L->list[j];

L->size--;

return 1;

}

}

int ListGet(SeqList L,int i,DataType *x)

//取顺序表L 中第i 个元素的值，取到则返回1，否则返回0

{

if(iL.size-1)

{

printf("参数i 不合法！\n");

return 0;

}

else

{

*x=L.list[i];

return 1;

}

}

int ListNotEmpty(SeqList L)

//判断该表是否为空

//如果表的总长度小于等于0，则说明该表为空，返回1

{

if(L.size

return 0;

else

return 1;

}

#endif

5. 主函数

#include

#include

#include

typedef char DataType;

#define MaxSize 10 //定义顺序表数组的最大值 #define MaxVertices 30 //定义顶点的最大值 #define MaxWeight 10000 // 定义无穷大的具体值

#include "AdjMGraph.h"

#include "AdjMGraphCreate.h"

#include "Dijkstra.h"

int main()

{

AdjMGraph g;

char a[]={"1","2","3","4","5","6"};

RowColWeight rcw[]={{0,1,10},{0,2,12},{1,3,16},{1,4,25},{2,0,4},{2,1,3}, {2,3,12},{2,5,8},{3,4,7},{5,3,2},{5,4,10}}; int i, n=6, e=11,j;

int distance[6], path[6][6];

CreatGraph(&g, a, n, rcw, e);

Dijkstra(g, 0, distance, path);

printf("从顶点v%c到其他各顶点的最短距离为:\n",g.Vertices.list[0]); for(i=0;i

printf("到顶点v%c的最短距离为%d\n",g.Vertices.list[i],distance[i]);

printf("\n从顶点v%c到其他各顶点最短路径为:\n",g.Vertices.list[0]); for(i=0;i

{

printf("\n到顶点v%c的最短路径为:",g.Vertices.list[i]); for(j=0;j

if(path[i][j]!=-1)

printf (" v%c ",g.Vertices.list[path[i][j]]);

}

return 0;

}

九、测试情况

程序运行结果