当前位置：文档之家 › 单源最短路径

单源最短路径

  • 格式：doc
  • 大小：430.00 KB
  • 文档页数：12

实验四：单源最短路径一．问题描述给定带权图G和源点V，对图进行遍历并求从V到G中其余各顶点的最短路径。

二．输入及结果输入：带全图G的各个顶点及各边的权值。

输出：Dijkstra算法的结果（用矩阵表示），并给出各最短路径长度。

三．需求分析1图的深度优先搜索①数组visited[i]用来表示顶点V[i]是否被访问过。

②递归调用函数2图的广度优先搜索①队列操作的相关函数②数组visited[i]用来表示顶点V[i]是否被访问过。

3单源最短路径①需要一个辅助变量D，它的每个分量D[i]表示当前所找到的从始点V到每个终点V[i]的最短路径长度。

它的初态为：若从V到V[i]有弧，则D[i]为弧上的权值；否则置D[i]为INFINITY。

②需要二元数组P[v][w]，值为1，则W是V0到V当前球的最短路径上的顶点。

③需要Final[v]，值为1当且仅当已经求得V0到V的最短路径。

④用带权的邻接矩阵来表示带权有向图，arcs[i][j]表示弧<vi,vj>上的权值。

⑤函数Locate来确定顶点对应的数组编号。

四．算法描述1图的深度优先搜索深度优先搜索可以从图中的某个顶点V出发，访问此顶点，然后依次从V的未被访问过的邻接点出发深度优先遍历图，直至所有和V有路径相通的顶点都被访问，若此时还有未被访问过的节点，则重复上述过程，开始深度搜索。

2图的广度优先搜索从图中某顶点V出发，在访问了V之后一次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问”，直至图中所有被已访问的顶点的邻接点都被访问到。

若此时图中尚有顶点未被访问，则另选图中未被访问的结点作为起始点，重复上述过程，直至图中所有顶点都被访问。

其中要用到队列的有关算法。

3单源最短路径①记S为已经找到的从源点出发的最短路径的点的集合，它的初始状态为空集。

那么，从V出发到图上其余各顶点V[i]可能达到的最短路径的初始值为D[i]=arcs[Locate Vex(G,V)][i].②选择Vj使得：D[j]=Min{D[i] ：vi S} ,Vj就是当前求得的一条从V出发的最短路径的终点。

将V[j]加入到S中。

③修改从V出发到集合V—S上任意顶点V[k]可达到的最短路径长度。

如果：D[j]+arcs[j][k]<D[k]，则修改D[k]为D[k]=D[j]+arcs[j][k];④重复操作（2）（3）N-1次。

由此求得从源点V到图上其余各顶点的最短路径是以路径长度递增的序列。

五．关键模块设计1深度优先搜索void dfs(MGraph *G,int i){int j;visited[i]=1;//标记VI，表示其已被访问printf("%5s",(*G).vexs[i]);for(j=0;j<(*G).vexnum;++j) //依次搜索VI的每个邻接点if((*G).arcs[i][j].adj!=INFINITY &&!visited[j])dfs(G,j);//递归调用}2.广度优先搜索void bfs(MGraph *G,int i){int j,k;VertexType x;SqQueue Q;Initqueue_sq(&Q,(*G).vexnum);visited1[i]=1;printf("\n%5s",(*G).vexs[i]);Enqueue_sq(&Q,(*G).vexs[i]); //已访问过的初始点入队while(!Queueempty(Q)){Dequeue_sq(&Q,x);k=LocateVex(*G,x);for(j=0;j<(*G).vexnum;++j){ //依次搜索Vi的每个可能的邻接点if(j!=k&&(*G).arcs[k][j].adj!=INFINITY &&!visited1[j]){visited1[j]=1;printf("%5s",(*G).vexs[j]);Enqueue_sq(&Q,(*G).vexs[j]);//顶点入队}}}}3单源最短路径//用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度//D[v]。

若P[v][w]为1,则w是从v0到v当前求得最短路径上的顶点。

//final[v]为1当且仅当v∈S,即已经求得从v0到v的最短路径void ShortestPath_DIJ(MGraph G,int v0,PathMatrix *P,ShortPathTable *D){int v,w,i,j,min,v1,w1;int final[MAX_VERTEX_NUM];for(v=0;v<G.vexnum;++v){final[v]=0;(*D)[v]=G.arcs[v0][v].adj;for(w=0;w<G.vexnum;++w)(*P)[v][w]=0; //设空路径if((*D)[v]<INFINITY){(*P)[v][v0]=1;(*P)[v][v]=1;}}printf("\nfinal[]:"); //打印初始状态for(v1=0;v1<G.vexnum;++v1)printf("%6d",final[v1]);printf("\n\nD[]:");for(v1=0;v1<G.vexnum;++v1)printf("%8d",(*D)[v1]);printf("\n\nP[][]:\n");for(v1=0;v1<G.vexnum;++v1){for(w1=0;w1<G.vexnum;++w1)printf("%6d",(*P)[v1][w1]);putchar('\n');}(*D)[v0]=0;final[v0]=1; //初始化,v0顶点属于S集for(i=1;i<G.vexnum;++i) //其余G.vexnum-1个顶点{ //开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集min=INFINITY; // 当前所知离v0顶点的最近距离for(w=0;w<G.vexnum;++w)if(!final[w]) //w顶点在V-S中if((*D)[w]<min){v=w;min=(*D)[w];} //w顶点离v0顶点更近final[v]=1; //离v0顶点最近的v加入S集printf("\nfinal[]:"); //打印中间结果，跟踪数据变化for(v1=0;v1<G.vexnum;++v1)printf("%6d",final[v1]);printf("\n\nD[]:");for(v1=0;v1<G.vexnum;++v1)printf("%6d",(*D)[v1]);printf("\n\nP[][]:\n");for(v1=0;v1<G.vexnum;++v1){for(w1=0;w1<G.vexnum;++w1)printf("%6d",(*P)[v1][w1]);putchar('\n');}for(w=0;w<G.vexnum;++w) //更新当前最短路径及距离if(!final[w]&&min<INFINITY && G.arcs[v][w].adj < INFINITY&& (min+G.arcs[v][w].adj<(*D)[w])){//修改D[w]和P[w],w∈V-S(*D)[w]=min+G.arcs[v][w].adj;for(j=0;j<G.vexnum;++j)(*P)[w][j]=(*P)[v][j];(*P)[w][w]=1;}}}六．调试运行及结果输入以下图：运行结果如下七．心得与体会在调试程序过程中，开始时老是广度优先搜索出错。

后来发现是队列的入队出了错，因为在程序中同时有了图和队列的数据结构，且他们都含有顶点这一项，导致在入队是直接将Q.elem[i]入队，实际上应为G.vexs[i]入队，平时的惯性思维导致了错误。

另外，起初想用链表进行搜索，后来发现结果不对，因为图是有向的，在链表的头结点和表结点连接时会有先后顺序之分，以致搜索结果会随输入的顺序改变而改变。

所以最后该为用矩阵进行搜索，并求最短路径。

附：源程序#include <stdio.h>#include <string.h>#include <malloc.h>#define MAX_NAME 10 //顶点字符串的最大长度+1#define MAX_INFO 20 //相关信息字符串的最大长度+1#define INFINITY 10000 //用10000代替∞#define MAX_VERTEX_NUM 20 //最大顶点个数#define QUEUE_INIT_SIZE 20 //队列长度typedef int VRType ; //顶点关系的数据类型typedef char VertexType[MAX_NAME]; //顶点数据类型及长度//邻接矩阵的数据结构typedef struct{VRType adj; //为权值类型,省去弧的其他相关信息}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图的数据结构typedef struct{VertexType vexs[MAX_VERTEX_NUM];// 顶点向量AdjMatrix arcs; //邻接矩阵int vexnum, //图的当前顶点数arcnum; //图的当前弧数} MGraph;//队列的数据结构typedef struct SqQueue{VertexType elem[MAX_VERTEX_NUM];int queuesize;int front,rear;}SqQueue;typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//路径矩阵typedef int ShortPathTable[MAX_VERTEX_NUM];//路径上的结点权int visited[MAX_VERTEX_NUM]={0},visited1[MAX_VERTEX_NUM]={0};//定位,若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。

合集下载

最短路径单源最短路径问题单源最短路径问题

最短路径单源最短路径问题单源最短路径问题


¾ 规律：当按长度增序生成从源s到其它顶点的最短路径时，则当前正 在生成的最短路径上除终点外，其余顶点的最短路径均已生成
¾ 例子：当求0到2的最短路径时，则该路径<0,3,2>上顶点0,3的最短路
径在此前已生成
2
§7.6.1 单源最短路径问题
约定 从源s到终点v的最短路径简称为v的最短路径，SP(v) s到v的最短路径长度简称为v的最短距离，SD(v) 红点集S：最短距离已确定的顶点集合 白点集V-S：最短距离尚未确定的顶点集合
6
1
§7.6.1 单源最短路径问题
例子
10 10
1
0
0 100 100
30 4
∞2
3 30
10 10
1
50
60 2
0 0 100
100 30 4
3 30
10 10
1
50 2
0 0
30
4 90
60
20 3 30
0
10 0
10 1
30
10
4 60
50 2 20 3 30
10 0 1 30 50 10
2 20
100
4 60 3
最短距离：红色 估计距离：白色 依次求出的最短距离为： 1) D[0]=0 2) D[1]=10，调整顶点2 3) D[3]=30，调整顶点2，4 4) D[2]=50，调整顶点4 5) D[4]=60
¾ 最短路径树：各顶点的最短路径（实线）总是一棵以源点为根的树，称之
为最短路径树。
算法思想- Dijkstra（1972图灵奖得主） 基于上述观察 初始化：仅已知源s的最短距离SD(s)=0，故红点集S={s}; 扩充红点集：算法的每一步均是在当前白点集中选一最短距离最小的白点 来扩充红点集，以保证算法是按长度增序来产生各顶点的最短路径; 结束：当前白点集空或仅剩下最短距离为∞的白点为止。注：若s到某白 点的路径不存在，可假设该白点的最短路径是一条长度为∞的虚拟路径。
bfs单源最短路径过程

bfs单源最短路径过程

bfs单源最短路径过程摘要：1.BFS 单源最短路径的定义2.BFS 算法的基本思想3.BFS 算法的具体操作步骤4.BFS 算法的优点和缺点5.BFS 算法的应用实例正文：一、BFS 单源最短路径的定义BFS（Breadth-First Search，广度优先搜索）单源最短路径是指从某个起始节点开始，以最短的路径到达目标节点的一种搜索算法。

这种算法适用于寻找无权图中的单源最短路径，也可用于解决带权图中的单源最短路径问题。

二、BFS 算法的基本思想BFS 算法的基本思想是：从起始节点开始，沿着当前未被访问过的节点进行搜索，逐层访问相邻节点，直到找到目标节点或访问完所有节点。

BFS 算法是一种贪心算法，每次选择距离起点最近的节点进行扩展，这样可以保证找到的路径是最短的。

三、BFS 算法的具体操作步骤1.创建一个队列（Queue），将起始节点加入队列。

2.当队列非空时，重复以下步骤：a.从队列中取出一个节点，将其标记为已访问。

b.遍历该节点的所有邻接节点，如果邻接节点未被访问且满足条件（例如在带权图中，邻接节点的距离不超过当前节点到目标节点的距离），则将该邻接节点加入队列，并标记为已访问。

3.如果目标节点被访问，则算法结束并返回找到的路径；否则，队列为空，说明不存在从起始节点到目标节点的路径。

四、BFS 算法的优点和缺点BFS 算法的优点是简单易懂，易于实现，适合用于寻找单源最短路径。

缺点是空间复杂度较高，需要额外的存储空间来存储访问过的节点，对于大型图来说，空间消耗可能较大。

此外，BFS 算法的时间复杂度为O(V+E)，其中V 表示节点数，E 表示边数，较慢于Dijkstra 算法等其他单源最短路径算法。

五、BFS 算法的应用实例BFS 算法在实际生活中有很多应用，例如网络爬虫、病毒传播、地图导航等。

bfs单源最短路径过程

bfs单源最短路径过程

bfs单源最短路径过程摘要：一、bfs 单源最短路径过程的介绍1.概念解释2.基本思想二、bfs 单源最短路径过程的具体步骤1.构建初始队列2.遍历邻接矩阵3.更新最短路径三、bfs 单源最短路径过程的应用1.举例说明2.实际应用场景四、总结1.优点2.缺点3.与其他算法的比较正文：bfs 单源最短路径过程是一种用于寻找无权图中从源节点到其他所有节点的最短路径的算法。

它的基本思想是从源节点开始，逐层向外扩展，将距离源节点最近的节点不断加入到队列中，直到队列为空或者所有节点都被遍历到。

具体来说，bfs 单源最短路径过程分为以下几个步骤：首先，构建一个初始队列，将源节点放入队列中。

然后，遍历邻接矩阵，取出队首节点，将其从队列中移除，并将该节点的所有邻接节点加入队列中。

同时，更新这些邻接节点的最短路径。

接下来，继续遍历邻接矩阵，重复上述步骤，直到队列为空或者所有节点都被遍历到。

最后，更新所有节点的最短路径，得到从源节点到其他所有节点的最短路径。

bfs 单源最短路径过程可以应用于很多场景，比如网络路由、基因测序、社交网络分析等。

以网络路由为例，我们可以将网络中的各个节点看作图中的节点，每条边看作图中的边，源节点则是需要发送数据包的源地址，通过bfs 单源最短路径过程可以找到从源地址到目的地址的最短路径。

总结来说，bfs 单源最短路径过程是一种简单有效的算法，其优点是时间复杂度为O(|V|+|E|)，空间复杂度为O(|V|)，且可以处理大规模的图。

缺点是对于有向图和存在负权边的图，该算法可能无法正确求解最短路径。

单源最短路径

单源最短路径

单源最短路径问题I 用贪心算法求解贪心算法是一种经典的算法，通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

一般具有2个重要的性质：贪心选择性质和最优子结构性质。

一、问题描述与分析单源最短路径问题是一个经典问题，给定带权有向图G =(V,E)，其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称为源。

现在要计算从源到所有其他各顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

分析过程：运用Dijkstra算法来解决单源最短路径问题。

具备贪心选择性质具有最优子结构性质计算复杂性二、算法设计（或算法步骤）用贪心算法解单源最短路径问题：1.算法思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。

设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。

一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。

2.算法步骤：(1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧<vi,vj>上的权值. 若<vi, vj>∉V,则置c[i][j]为∞。

设S为已知最短路径的终点的集合,它的初始状态为空集。

从源点v到图上其余各点vi的当前最短路径长度的初值为：dist[i]=c[v][i] vi∈V。

(2) 选择vj, 使得dist[j]=Min{dist[i] | vi∈V-S}，vj就是长度最短的最短路径的终点。

令S=SU{j}。

的当前最短路径长度:(3) 修改从v到集合V-S上任一顶点vk如果dist[j]+c[j][k]< dist[k] 则修改dist[K]= dist[j]+c[j][k](4) 重复操作(2),(3)共n-1次.三、算法实现#include <iostream>#include <stdlib.h>using namespace std;#define MAX 1000000 //充当"无穷大"#define LEN sizeof(struct V_sub_S)#define N 5#define NULL 0int s; //输入的源点int D[N]; //记录最短路径int S[N]; //最短距离已确定的顶点集const int G[N][N] = { {0, 10, MAX, 30, 100},{MAX, 0, 50, MAX, MAX},{MAX, MAX, 0, MAX, 10},{MAX, MAX, 20, 0, 60},{MAX, MAX, MAX, MAX, 0} };typedef struct V_sub_S //V-S链表{int num;struct V_sub_S *next;};struct V_sub_S *create(){struct V_sub_S *head, *p1, *p2;int n = 0;head = NULL;p1 = (V_sub_S *)malloc(LEN);p1->num = s;head = p1;for(int i = 0; i < N+1; i ++){if(i != s){++ n;if(n == 1)head = p1;elsep2->next = p1;p2 = p1;p1 = (V_sub_S *)malloc(LEN);p1->num = i;p1->next = NULL;}}free(p1);return head;}struct V_sub_S *DelMin(V_sub_S *head, int i) //删除链表中值为i 的结点{V_sub_S *p1, *p2;p1 = head;while(i != p1->num && p1->next !=NULL){p2 = p1;p1 = p1->next;}p2->next = p1->next;return head;}void Dijkstra(V_sub_S *head, int s){struct V_sub_S *p;int min;S[0] = s;for(int i = 0; i < N; i ++){D[i] = G[s][i];}for(i = 1; i < N; i ++){p = head->next;min = p->num;while(p->next != NULL){if(D[p->num] > D[(p->next)->num])min = (p->next)->num;p = p->next;}S[i] = min;head = DelMin(head, min);p = head->next;while(p != NULL){if(D[p->num] > D[min] + G[min][p->num]){D[p->num] = D[min] + G[min][p->num];}p = p->next;}}}void Print(struct V_sub_S *head){struct V_sub_S *p;p = head->next;while(p != NULL){if(D[p->num] != MAX){cout << "D[" << p->num << "]: " << D[p->num] << endl;p = p->next;}else{cout << "D[" << p->num << "]: " << "∞" << endl;p = p->next;}}}int main(){struct V_sub_S *head;cout << "输入源点s (0到4之间): ";cin >> s;head = create();Dijkstra(head, s);head = create();Print(head);system("pause");return 0;}运行结果：四、算法分析（与改进）对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。