浅谈【数据结构】图-最短路径问题

本文主要是介绍浅谈【数据结构】图-最短路径问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1、最短路径问题

2、迪杰斯特拉算法

3、算法的步骤

---

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

---

1、最短路径问题

最短路径问题：是指在图中找到两个顶点，求两个顶点之间最短路径的一个问题。

“最短”：通常来说是指路径上面总权值最小，权值（边/弧的长度、成本、时间...）。

最短路径问题计算机科学、运筹学、网络理论等多个领域都有广泛的应用。

在图中，路径是指：一个顶点到另一个顶点的方式。一个顶点到另一个顶点方式并不一定是唯一的，在 多个路径中找一个总权值最小的一个路径。

解决带权的有向图两个顶点之间最短路径问题

两个经典算法：

• 迪杰斯特拉算法（Dijkstra）
• 弗洛伊德算法（Floyd）

2、迪杰斯特拉算法

Dijkstra算法：是解决从网络中任意一个顶点（源点）出发，求它到其他顶点（终点）的最短路径的问题。

算法思路：按路径长度递增次序产生从某个源点v到图中其余各项顶点的最短路径

Dijkstra算法依赖两个辅助向量：

• 向量S[n]
  • S[i]==1 (true)，说明从源点v到终点vi的最短路径已经找到了。
  • S[i]==0 (false) , 说明从源点v到终点vi的最短路径还没有找到。
  • 初始化开始S[v]==1 (true) , 其余各项顶点均为0 (false)。
• 向量dist[n]
  • dist[n]存放从源点v到终点vi这个顶点当前的最短路径
  • 初始化
    • 当v可以直接到到vi的时候，那么dist[vi] = 的权值w
    • 当v不可以直接到到vi的时候，那么dist[vi] = 无穷大

3、算法的步骤

很显然从源点v到其它各项顶点的最短路径中的第一短的路径，绝对是能直接到到达的顶点（邻接点）中 最短的一条路径

• 第一步：
  • 从源点v到其它各项顶点的当前最短路径找出最短的来。
    • dist[u] = min{dist[w] (w=0,1,2,3,4,5....n-1),并且S[w]==0 (false))}
      • 最优路径=当前已知的最短路径中最短的一条
    • dist[u] 称为当前最优路径，u为当前最优的顶点下标
• 第二步：
  • 用当前最优路径来更新其他的路径
    • 对S[w] == 0 的w（没有找到最优路径的顶点）进行更新。
    • 如果dist[u]+ 小于 dist[w] , 那么就更新dist[w]
• 第三步：
  • 重复第一步和第二步

***迪杰斯特拉算法代码示例***

#include <iostream>// 顶点数量是10个
#define VertexMaxCount 10// 无穷大
#define MAXNUMBER (65535)// 图类型
typedef struct 
{// 关系集int R[VertexMaxCount][VertexMaxCount];// 顶点集std::string V[VertexMaxCount];// 顶点数量int vertex_count;
}Graph;// 关系类型
typedef  struct 
{int index_s; // 关系开始顶点下标int index_e; // 关系结束顶点下标int r;  // 关系
}R;/*@brief 为一个邻接矩阵图增加一个顶点@param graph  需要增加顶点的图指针@param vertex 需要增加的顶点
*/
void addVertex(Graph *graph,std::string vertex)
{// 判断图是否存在if(!graph)return;// 添加新顶点graph->V[graph->vertex_count] = vertex;// 更新顶点数量graph->vertex_count++;
}int getIndex(Graph*graph,std::string vertex)
{if(!graph)return -1;for(int index=0;index < VertexMaxCount;index++)if(graph->V[index] == vertex)return index; // 返回顶点在图中的下标return -1; // 表示顶点不在图中
}/*@brief 为一个邻接矩阵图增加关系@param graph 需要增加关系的图指针@param r 增加新关系
*/
void addR(Graph *graph,R r)
{// 判断图是否存在if(!graph)return;// 添加关系graph->R[r.index_s][r.index_e] = r.r;
}Graph *creatGraph()
{// 申请了一个邻接矩阵的空间Graph * graph = new Graph;std::cout << "请依次输入顶点：";// 增加顶点while(1){std::string vertex = "结束";std::cin >> vertex;if(vertex == "结束")break; // 增加进入图addVertex(graph,vertex);}// 先初始化关系for(int row = 0;row < VertexMaxCount;row++){for(int column = 0;column < VertexMaxCount;column++)if(row == column)graph->R[row][column] = 0;elsegraph->R[row][column] = MAXNUMBER;}std::cout << "请输入顶点之间的关系：" << std::endl;// 增加关系while(1){std::string start_vertex = "结束";std::string end_vertex = "结束";int ralation = MAXNUMBER;std::cin >> start_vertex;std::cin >> end_vertex;std::cin >> ralation;if(start_vertex == "结束"||end_vertex == "结束"||ralation == MAXNUMBER)break;R r;r.index_s = getIndex(graph,start_vertex);r.index_e = getIndex(graph,end_vertex);r.r = ralation;// 判断结点下班是否有效if(r.index_s == -1||r.index_e == -1)continue;// 存入关系addR(graph,r);}return graph;
}/*@brief 打印一个邻接矩阵图@param graph 需要打印的邻接矩阵图指针
*/
void printGraph(Graph *graph)
{if(!graph)return ;std::cout << "\t";// 打印顶点for(int count=0;count < VertexMaxCount;count++)std::cout << graph->V[count] << "\t";std::cout << std::endl;// 打印关系for(int row = 0;row < graph->vertex_count;row++){std::cout << graph->V[row] << "\t";for(int column = 0;column < VertexMaxCount;column++){// 存在关系std::cout << graph->R[row][column] << "\t";}std::cout << std::endl;}
}/*逻辑思路：算法的步骤很显然从源点v到其它各项顶点的最短路径中的第一短的路径，绝对是能直接到到达的顶点（邻接点）中最短的一条路径- 第一步：- 从源点v到其它各项顶点的当前最短路径找出最短的来。- dist[u] = min{dist[w] (w=0,1,2,3,4,5....n-1),并且S[w]==0 (false))}- 最优路径=当前已知的最短路径中最短的一条- dist[u] 称为**当前最优路径**，u为当前最优的顶点下标- 第二步：- 用当前最优路径来更新其他的路径- 对S[w] == 0 的w（没有找到最优路径的顶点）进行更新。- 如果dist[u]+<u,w> 小于 dist[w] , 那么就更新dist[w]- 第三步：- 重复第一步和第二步@brief 通过迪杰斯特拉算法求最短路径@param graph 需要进行最短路径查找的图@param v_src 源点
*/// 两个辅助向量
static bool  S[VertexMaxCount];
static int dist[VertexMaxCount];void Dijkstra(Graph *graph,std::string v_src)
{
//------------------------迪杰斯特拉准备工作---------------------------// 初始化向量Sfor(int count = 0;count < graph->vertex_count;count++)S[count] = false; // 把所有顶点初始化的时候置为没有找到最短路径// 将v_src 到 v_src设置为找到了最短路径:自己到自己的最优路径找到了int v_src_pos = getIndex(graph,v_src);S[v_src_pos] = true;// 初始化dist向量for(int count = 0;count < graph->vertex_count;count++)dist[count] = graph->R[v_src_pos][count]; // 权值存储到dist里面// 结束之后：dist存储了源点到其他顶点的路径权值//------------------------正式开始迪杰斯特拉---------------------------int min_pos; // 用来存储当前最短路径的下标int min_w;   // 用来存储当前最短路径的权值for(int count = 0;count < graph->vertex_count-1;count++){// 初始化当前最短路径的下标和权值min_pos = 0;min_w = MAXNUMBER;// 第一步：从源点v到其他各项顶点的当前最短路径中找出最短的路径for(int min_road_pos = 0;min_road_pos < graph->vertex_count;min_road_pos++){// 最优路径=当前已知的最短路径中最短的一条if(S[min_road_pos]==false&&dist[min_road_pos] < min_w){min_pos = min_road_pos; // 保存小的那个下标min_w   = dist[min_road_pos]; // 保存它的权值}}// 当循环结束，你就能拿到当前最短路径中的第一短std::cout << "当前最短路径为:" << graph->V[v_src_pos] << "->" << graph->V[min_pos] << ":" << min_w << std::endl;// 这一条路径是源点到min_pos顶点的最优路径了，标记它S[min_pos] = true;// 第二步：通过这个最短路径来更新其他顶点路径for(int pos = 0;pos < graph->vertex_count;pos++){//  如果dist[min_pos]+<min_pos,pos> 小于 dist[pos] , 那么就更新dist[pos]if(S[pos] == false&&dist[min_pos]+graph->R[min_pos][pos] < dist[pos]){// 更新pos对应的顶点的路径dist[pos] = dist[min_pos] + graph->R[min_pos][pos];}}}// 整个循环结束之后，从v_src到其他各项顶点的最短路径就求出来了for(int count = 0; count < graph->vertex_count;count ++){std::cout << graph->V[v_src_pos] << "->" << graph->V[count] << ":" << dist[count] << std::endl;}
}int main()
{Graph *g = creatGraph();printGraph(g);Dijkstra(g,"a");delete g;return 0;
}

这篇关于浅谈【数据结构】图-最短路径问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---