图最短路问题

xiaoxiao2022-07-13 157

图的最短路问题分类

求解最短路问题有很多种解决方案，各个方案会有对应的解决类型单源最短路问题：BFS用于解决单源无权最短路问题 Dijkstra算法用于解决单源正权最短路问题各顶点最短路问题：Floyd算法

一、BFS广度优先搜索

1、BFS按照到源点的最短距离①将图中的各点分类，按照距离从小到大访问各点。为了实现按距离大小访问各点，BFS引入了队列来存放待访问的节点。 ① 这里的距离指的是源点到该点通过了几条边

2、算法描述 E1、先将源点入队，并把d[源] = 0； E2、弹出队首元素(q_top)，将q_top的邻接节点q_adjacent入队，并d[q_adjacent] = d[q_top] + 1； E3、执行E2直到队空；

3、具体代码

#include<iostream> #include<queue> #include<cstring> using namespace std; const int MAX = 100; //最大储存点数 struct node { int value; int to; struct node *next; }; struct node *(head[MAX]); //邻接表表头 int head_sum; //当前图中节点数 void BuildGraph(void); void BFS(void); int main(void) { BuildGraph(); BFS(); return 0; } void BuildGraph(void) //创建链接表 { int m, n; cout << "请输入创建的节点数和边数"; cin >> m >> n; head_sum = m; for (int i = 1; i <= m; i++) //给head分配空间 { head[i] = new struct node; head[i]->next = NULL; head[i]->value = i; } cout << "按照起点终点权值的方式输入图节点"; for (int i = 0; i < n; i++) { int a, b, c; cin >> a >> b >> c; if (head[a]->next == NULL) //连接 b 到 head[a] { head[a]->next = new struct node; head[a]->next->to = b; head[a]->next->value = c; head[a]->next->next = NULL; } else { struct node *scan = head[a]->next; while (1) { if (scan->next == NULL) break; scan = scan->next; } scan->next = new struct node; scan = scan->next; scan->to = b; scan->value = c; scan->next = NULL; } if (head[b]->next == NULL) //连接 a 到 head[b] { head[b]->next = new struct node; head[b]->next->to = a; head[b]->next->value = c; head[b]->next->next = NULL; } else { struct node *scan = head[b]->next; while (1) { if (scan->next == NULL) break; scan = scan->next; } scan->next = new struct node; scan = scan->next; scan->to = a; scan->value = c; scan->next = NULL; } } } void BFS(void) { queue<int> q; int flag[10000]; memset(flag, 0, sizeof(flag)); cout << "请选择从哪个节点开始遍历："; int tem; cin >> tem; fflush(stdin); if (tem > head_sum) { cout << "总共只有" << head_sum << "个节点，无法从该节点开始遍历"; return; } if (tem <= 0) { cout << "节点名称都是正整数，无法从该节点开始\n"; return; } q.push(tem); flag[tem] = 1; while (!q.empty()) { int now = q.front(); q.pop(); cout << now << " "; struct node *scan = head[now]->next; while (scan != NULL) { if (flag[scan->to] == 0) { q.push(scan->to); flag[scan->to] = 1; } scan = scan->next; } } }

二、Dijkstra算法

1、Dijksta算法是将图中的顶点分为两个集合（已定最短路径的点集与未定最短路的点集），不断地选取跨越两个集合的边中最小的那一个，并将这个边端点都放入已定集合当中，迭代地进行处理最终使所有边都放入已定集合中。

2、算法描述在代码示例中用到了这样几个数据： Graph[][]：图中对应路径的权重； from：源点，也就是起点（我的代码中代表了起点编号）； dist[]：源点到各个点的距离； flag[]：标记已经去过的点（即已定最短路径的点集）； v[]：用于记录最短路径（v[i] == j：表示最短路径中有一段时<j , i>，用于最后输出完整的最短路径）

E1、将dist[]初始化为INF（表示无法到达）并将flag[]初始化为0（表示不在最短路径的点集中），再将dist[from] = 0、flag[from] = 1、from能到达的点to的dist[to] = Graph[from][to]； E2、不断选取一个未被选过的、dist最小的顶点u，对他能直接一步到达的顶点j进行松弛操作②并对顶点u进行标记,直到所有顶点都被选过； ② 如果dist[j]有更好的选择（dist[j] > dist[u] + Graph[u][j]）那么我们就对j进行松弛（dist[j] = dist[u] + Graph[u][j]），并保存u、j之间的连接关系：v[j] = u;

3、结果最终dist[]中保存的就是源点到各个顶点的距离，可以利用v[]来输出源点到各个顶点的最短路径。

4、具体代码

//使用邻接表来储存有向有权图 //默认图中每个点都有自己的一个编号，从1开始 /*测试数据 1 2 5 2 3 6 3 5 1 2 4 9 5 1 6 5 4 9 2 6 3 2 5 8 -1 -1 -1 */ #include<iostream> #include<cstdlib> #include<cstring> #include<stack> using namespace std; const int MAX = 100; const int INF = 1000000; struct node{ //邻接表中的节点 int point; //终点编号 int weight; //边的权重 struct node *next; }; struct node *(head[MAX]); //邻接表，最多MAX个元素 int point_sum; void Dij(int src , int *dist , int *flag , int *v); void Print(int src , int *dist , int *v); int main(void) { for(int i = 0 ; i < MAX ; i++) { head[i] = new struct node; head[i]->next = NULL; } cout << "按起点终点权重的方式输入（-1 -1 -1来结束）\n"; while(1) //输入数据建图 { int f , t , w; cin >> f >> t >> w; if(f == -1 && t == -1 && w == -1) break; struct node *scan = head[f]; while(scan->next != NULL) scan = scan->next; scan->next = new struct node; scan = scan->next; scan->point = t; scan->weight = w; scan->next = NULL; if(f > point_sum || t > point_sum) point_sum = f > t ? f : t; } int src , dist[MAX] , flag[MAX] , v[MAX]; //dist[]保存源点到各个点的最短路径长度，flag[]标记已经走过的路，v[]存储最短路径 cout << "确定源点："; cin >> src; Dij(src , dist , flag , v); Print(src , dist , v); return 0; } void Dij(int src , int *dist , int *flag , int *v) { //初始化 for(int i = 1 ; i <= point_sum ; i++) dist[i] = INF; memset(flag , 0 , sizeof(flag)); memset(v , 0 , sizeof(v)); //将src能到达的点进行第一次更新 dist[src] = 0; flag[src] = 1; for(struct node *scan = head[src]->next ; scan != NULL ; scan = scan->next) { int &point = scan->point; int &weight = scan->weight; dist[point] = weight; v[point] = src; } //循环求解最短路 for(int i = 1 ; i < point_sum ; i++) //一共进行 point_sum-1 次 { int min = INF , u; for(int j = 1 ; j <= point_sum ; j++) if(dist[j] < min && flag[j] == 0) //选取当前dist中最小的一个 { min = dist[j]; u = j; } flag[u] = 1; for(struct node *scan = head[u]->next ; scan != NULL ; scan = scan->next) //对编号为u的点所能一次移动就能到达的点进行松弛 { int &point = scan->point; int &weight = scan->weight; if(dist[u] + weight < dist[point]) { dist[point] = dist[u] + weight; v[point] = u; } } } //得到最短路及其长度 } void Print(int src , int *dist , int *v) //打印最短路长度及其路径 { for(int i = 1 ; i <= point_sum ; i++) { if(dist[i] == INF) { cout << "源点无法到达" << i << "点" << endl; continue; } cout << "源点到" << i << "的最短路径长度为：" << dist[i] << endl; cout << "路径为"; stack<int> path; //用栈来模拟输出，因为如果直接输出，点序列是倒过来的 int now = i; while(now != src) { path.push(now); now = v[now]; } cout << src << ' '; while(!path.empty()) { cout << "->" << path.top(); path.pop(); } cout << endl; } }

三、Floyd算法

用到的变量名称：A[][]：最重要的一个量，算法执行过程中不断会更新的一个量，A[i][j]表示任意两点之间的最短路径长度； 1、Floyd算法是基于动态规划的思想，利用动态规划解决问题最重要的就是状态转移方程，Floyd算法的状态转移方程： A(k)[i][j] = min { A(k-1)[i][j]，A(k-1)[i][k] + A(k-1)[k][j] }, k = 1,2,…, n 状态转移方程表达的是前后两个状态之间的关系； A(k)[i][j]：该式的值表示当前点i 和 j的最短路径长度，该式表示的逻辑意义是i 到 j的最短路中只考虑前k个点，也就是说，当前点i 到 j的最短路只会包含 1、2、3…k 这k个点，暂时与之后的点无关。

状态转移方程所表达的意思是：要想找到点 i 和 j 之间的最短路径长度，那么我们只需要选取A(k-1)[i][j]和A(k-1)[i][k] + A(k-1)[k][j]中较小的一个（这个也就是Floyd算法中最基础的操作：松弛操作）。

2、算法描述假设邻接矩阵存储图，edge[n][n]为图的邻接矩阵； E1、定义初始矩阵A(0) [i][j] = edge[i][j]； E2、求A(1),即从vi到vj 经由顶点可以是{v1}的最短路径； E3、求A(2),即从vi 到vj 经由顶点可以是{v1, v2}的最短路径； … E(n+1)、求A(n),即从vi 到vj 经由顶点可以是{v1, v2,…,vn}的最短路径长度；最后A(n)即为所求的任意两点间最短路径长度

3、具体代码

//有权有向图用邻接矩阵edge存储 //点编号默认从1开始 /* 测试数据 1 2 3 3 2 4 2 5 1 2 1 6 3 5 4 1 5 6 5 6 7 -1 -1 -1 */ #include<iostream> #include<cstring> #include<cstdlib> #include<stack> using namespace std; const int MAX = 100; //最大存储点的个数 const int INF = 100000; int edge[MAX][MAX]; //用邻接矩阵存储 int point_sum = 0; void Floyd(int A[MAX][MAX] , int path[MAX][MAX]); void Print(int A[MAX][MAX] , int path[MAX][MAX]); int main(void) { //建图 for(int i = 1 ; i < MAX ; i++) for(int j = 1 ; j < MAX ; j++) edge[i][j] = INF; for(int i = 1 ; i < MAX ; i++) edge[i][i] = 0; cout << "输入起终点编号权值（以-1 -1 -1结束）\n"; while(1) { int from , to , weight; cin >> from >> to >> weight; if(from == -1 && to == -1 && weight == -1) break; edge[from][to] = weight; if(from > point_sum || to > point_sum) point_sum = from > to ? from : to; } //执行算法 int A[MAX][MAX] , path[MAX][MAX]; Floyd(A , path); //输出执行结果 Print(A , path); } void Floyd(int A[MAX][MAX] , int path[MAX][MAX]) { //初始化 for(int i = 1 ; i <= point_sum ; i++) for(int j = 1 ; j <= point_sum ; j++) A[i][j] = edge[i][j]; memset(path , 0 , sizeof(path)); //求状态方程——最关键的地方 for(int k = 1 ; k <= point_sum ; k++) //注意这里最外层循环应该是状态转移方程中的 k for(int i = 1 ; i <= point_sum ; i++) for(int j = 1 ; j <= point_sum ; j++) { if(A[i][k] + A[k][j] < A[i][j]) { A[i][j] = A[i][k] + A[k][j]; path[i][j] = k; } } } void Print(int A[MAX][MAX] , int path[MAX][MAX]) { for(int i = 1 ; i <= point_sum ; i++) { for(int j = 1 ; j <= point_sum ; j++) { if(A[i][j] == INF) { cout << i << "到" << j << "之间没有路" << endl; continue; } stack<int> p; p.push(j); int now = path[i][j]; while(now != 0) { p.push(now); now = path[i][now]; } cout << "从" << i << "到" << j << "最短路长度：" << A[i][j] << endl; cout << "最短路径为：" << i << ' '; while(!p.empty()) { cout << "->" << p.top(); p.pop(); } cout << endl; } } }

后记

图的基本算法中还有Bellman-Ford算法以及他的优化版本SPFA，这两种算法也是用于处理单源最短路问题，相较于Dijkstra算法，这两个算法的优点在于他可以处理含有负权边的最短路问题（注意不是含有负权环，有负权环的图是没有最短路的）

最新回复(0)