单源最短路径
单源结点最短路径一、题目
单源结点最短路径问题。
二、问题描述
求从有向图的某一结点出发到其余各结点的最短路径。
三、基本要求
（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;
}
九、测试情况
程序运行结果
绛旓細鎬荤粨鏉ヨ锛Dijkstra绠楁硶鏄竴绉嶉潪甯告湁鏁堝拰甯哥敤鐨勫崟婧愭渶鐭矾寰勭畻娉锛屽畠鍦ㄨ矾寰勬悳绱佺綉缁滀紭鍖栥佷氦閫氳鍒掔瓑棰嗗煙鏈夌潃骞挎硾鐨勫簲鐢ㄣ傞氳繃閫愭璁块棶鍜屾洿鏂拌妭鐐圭殑鏈鐭矾寰勶紝Dijkstra绠楁硶鑳藉甯姪鎴戜滑鎵惧埌浠庤捣濮嬭妭鐐瑰埌鎵鏈夊叾浠栬妭鐐圭殑鏈浼樿矾寰勩
绛旓細Dijkstra绠楁硶锛岀炕璇戜綔鎴村厠鏂壒鎷夌畻娉曟垨杩澃鏂壒鎷夌畻娉曪紝浜1956骞寸敱鑽峰叞璁＄畻鏈虹瀛﹀鑹惧吂璧皵.鎴村厠鏂壒鎷夋彁鍑猴紝鐢ㄤ簬瑙ｅ喅璧嬫潈鏈夊悜鍥剧殑 鍗曟簮鏈鐭矾寰勯棶棰 銆傛墍璋撳崟婧愭渶鐭矾寰勯棶棰樻槸鎸囩‘瀹氳捣鐐癸紝瀵绘壘璇ヨ妭鐐瑰埌鍥句腑浠绘剰鑺傜偣鐨勬渶鐭矾寰勶紝绠楁硶鍙敤浜庡鎵句袱涓煄甯備腑鐨勬渶鐭矾寰勬垨鏄В鍐宠憲鍚嶇殑鏃呰鍟嗛棶棰樸傞棶棰樻弿杩 锛...
绛旓細Dijkstra绠楁硶Dijkstra's Algorithm锛欴ijkstra绠楁硶鐢ㄤ簬姹傝В鍗曟簮鏈鐭矾寰勯棶棰橈紝鍗充粠缁欏畾璧风偣鍒板叾瀹冩墍鏈夎妭鐐圭殑鏈鐭矾寰勩傚畠閫氳繃閫愭鎵╁睍璺緞闀垮害鏉ヤ笉鏂‘瀹氬綋鍓嶈窛绂昏捣鐐规渶杩戠殑鑺傜偣锛屽苟鏇存柊鍏跺畠鑺傜偣鐨勮窛绂诲硷紝鐩村埌鎵惧埌鎵鏈夎妭鐐圭殑鏈鐭矾寰勩傝礉灏旀浖绂忕壒绠楁硶Bellman-Ford Algorithm锛氳礉灏旀浖-绂忕壒绠楁硶鐢ㄤ簬姹傝В鍗曟簮鏈鐭矾寰勯棶...
绛旓細 Dijkstra绠楁硶鏄敱鑽峰叞璁＄畻鏈虹瀛﹀ Edsger Wybe Dijkstra浜1959骞存彁鍑虹殑鍗曟簮鐐规渶鐭矾寰勭畻娉曪紙SSSP:Single Souce Shortest Path锛夈傛槸涓涓В鍐冲姞鏉冨浘锛堜笉鍚礋鏉冮噸鐨勮竟锛変腑浠庝竴涓《鐐瑰埌鍏朵綑鍚勪釜椤剁偣鏈鐭矾寰勯棶棰樼殑绠楁硶銆侱ijkstra绠楁硶鏄竴涓泦 璐績绠楁硶 锛 骞垮害浼樺厛鎼滅储锛圔FS锛 鍜 鍔ㄦ佽鍒...
绛旓細鍗曟簮缁撶偣鏈鐭矾寰 涓銆侀鐩 鍗曟簮缁撶偣鏈鐭矾寰勯棶棰樸 浜屻侀棶棰樻弿杩 姹備粠鏈夊悜鍥剧殑鏌愪竴缁撶偣鍑哄彂鍒板叾浣欏悇缁撶偣鐨勬渶鐭矾寰勩 涓夈佸熀鏈姹 (1) 鏈夊悜鍥鹃噰鐢ㄩ偦鎺ョ煩闃佃〃绀恒 (2) 鍗曟簮缁撶偣鐨勬渶鐭矾寰勯棶棰橀噰鐢ㄧ媱鍏嬫柉鐗规媺绠楁硶銆 (3) 杈撳嚭鏈夊悜鍥句腑浠庢簮缁撶偣鍒板叾浣欏悇缁撶偣鐨勬渶鐭矾寰勫拰鏈鐭矾寰勫笺 鍥涖佹祴璇曟暟鎹 娴嬭瘯鏁...
绛旓細鏄俤ijkstra绠楁硶锛氭眰涓涓偣鍒板叾浠栭《鐐圭殑鏈鐭矾寰勶紝涔熷彨鍋氣滃崟婧愭渶鐭矾寰勨濓紝渚嬪1鍒板叾浠栬妭鐐圭殑鏈鐭矾寰勩傚綋n>m鏃讹紝鏄睘浜嶯P瀹屽叏闅鹃锛岃縿浠婃湭鏈夋晥瑙ｅ喅锛岃В棰樻濊矾Dijkstra绠楁硶鏄В鍐冲崟婧愭渶鐭矾寰勯棶棰樼殑璐績绠楁硶銆
绛旓細鍙傝冿細 Bellman-Ford 鍗曟簮鏈鐭矾寰绠楁硶 Bellman-ford 绠楁硶 Bellman-Ford 绠楁硶鏄竴绉嶇敤浜庤绠楀甫鏉冩湁鍚戝浘涓崟婧愭渶鐭矾寰勶紙SSSP锛歋ingle-Source Shortest Path锛夌殑绠楁硶 瀵逛簬甯︽潈鏈夊悜鍥 G = (V, E)锛孌ijkstra 绠楁硶瑕佹眰鍥 G 涓竟鐨勬潈鍊煎潎涓洪潪璐燂紝鑰孊ellman-ford鑳介傚簲涓鑸殑鎯呭喌锛堝嵆 瀛樺湪璐熸潈...
绛旓細浠庝竴涓簮鐐瑰埌鍏朵粬鍚勭偣鐨勬渶鐭矾寰勬槸鈥鍗曟簮鏈鐭矾寰鈥濊繕鏈夋瘡涓瀵归《鐐逛箣闂寸殑鏈鐭矾寰勶紝閭ｄ箞鏈鐭矾寰勬槸杩欎袱鑰呯殑缁熺О
绛旓細鎵璋撳崟婧愭渶鐭矾寰勯棶棰樻槸鎸囷細宸茬煡鍥綠=锛圴锛孍锛夛紝鎴戜滑甯屾湜鎵惧嚭浠庢煇缁欏畾鐨勬簮缁撶偣S鈭圴鍒癡涓殑姣忎釜缁撶偣鐨勬渶鐭矾寰勩傞鍏堬紝鎴戜滑鍙互鍙戠幇鏈夎繖鏍蜂竴涓簨瀹烇細濡傛灉P鏄疓涓粠vs鍒皏j鐨勬渶鐭矾锛寁i鏄疨涓殑涓涓偣锛岄偅涔堬紝浠巚s娌縋鍒皏i鐨勮矾鏄粠vs鍒皏i鐨勬渶鐭矾銆傛渶鐭矾寰勭畻娉 Dijkstra绠楁硶锛堣开鏉版柉鐗规媺锛夋槸鍏稿瀷鐨...
绛旓細鏈鐭矾寰dijkstra绠楁硶濡備笅: Dijkstra杩澃鏂壒鎷夋槸涓绉嶅鐞鍗曟簮鐐圭殑鏈鐭矾寰勭畻娉,灏辨槸璇存眰浠庢煇涓涓妭鐐瑰埌鍏朵粬鎵鏈夎妭鐐圭殑鏈鐭矾寰勫氨鏄疍ijkstra銆 璧勬枡鎷撳睍: 杩澃鏂壒鎷夌畻娉(Dijkstra)鏄敱鑽峰叞鏁拌厰璁＄畻鏈虹瀛﹀鐙勫厠鏂壒鎷変簬1959骞存彁鍑虹殑,鍥犳鍙堝彨鐙勫厠鏂壒鎷夌畻娉曘傛槸浠庝竴涓《鐐瑰埌鍏惰柉绾宠～浣欏悇椤剁偣鐨勬渶鐭矾寰勭畻娉,瑙ｅ喅鐨...
