下载文档原格式
最短路最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。
最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。
单源最短路径包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。
在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
）算法可以采用Dijkstra 算法。
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法代码1#include <string.h>2#include<algorithm>3using namespace std;45const int maxnum = 100;6const int maxint = 99999999;78int dist[maxnum];9int prev[maxnum];//记录当前点的前一个结点10int c[maxnum][maxnum];11int n,line;1213void dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum])//v代表源点14{15 bool s[maxnum];//判断是否已存入该点到S中16 for(int i = 1;i <= n;++i)17 {18 dist[i] = c[v][i];19 s[i] = 0;20 if(dist[i] == maxint)//代表当前点与源点没有直接相连21 prev[i] = 0;22 else23 prev[i] = v;//代表当前点的前一个节点是v，即源点24 }25 dist[v] = 0;//源点到源点的距离初始化为026 s[v] = 1;//源点已被遍历过，标记为12728 for(int i = 2;i <= n;++i)29 {30 int tmp = maxint;31 int u = v;32 for(int j = 1;j <= n;++j)33 {34 if((!s[j]) && dist[j] <tmp)//该点没有被遍历到并且源点到j点的距离小于记录的距离35 {36u = j;//记录下这一点37tmp = dist[j];//记录下这一点到源点的距离38 }39 }40 //找到距离最短的点退出循环41 s[u] = 1;//标记该点已经遍历过4243 for(int j = 1;j <= n;++j)44 {45 if((!s[j]) && c[u][j] <maxint)//j没有被遍历过并且从u到j还有这条路径46 {47 int newdist = dist[u] + c[u][j];//新的距离是从源点到u的距离加上从u到的距离48 if(newdist <dist[j])//如果新的距离比原来到j的距离要短49 {50 dist[j] = newdist;//则更新dist数组51 prev[j] = u;//标记j的前一个节点是u52 }53 }54 }55 }56}5758void searchpath(int *prev,int v,int u)//查找从v到u的最短路径59{60 int que[maxnum];//保存路径61 int tot = 1;62 que[tot] = u;//把终点存入路径数组63 tot++;64 int tmp = prev[u];65 while(tmp != v)66 {67 que[tot] = tmp;68 tot++;69tmp = prev[tmp];70 }71 que[tot] = v;72 for(int i = tot;i >= 1;--i)73 {74 if(i != 1)75 printf("%d->",que[i]);76 else77 printf("%d\n",que[i]);78 }79}808182int main()83{84 scanf("%d",&n);//输入结点数85 scanf("%d",&line);//输入路径数目86 int p,q,len;87 for(int i = 1;i <= n;++i)//初始化存储数组88 {89 for(int j = 1;j <= n;++j)90 {91 c[i][j] = maxint;92 }93 }94 for(int i = 1;i <= line;++i)//往存储数组里存放路径95 {96 scanf("%d%d%d",&p,&q,&len);97 if(len <c[p][q])//如果两个点之间有多条路，取路径较短的那一条98 c[p][q] = len;99 c[q][p] = len;//该语句根据实际情况写，用于无向路径中100 }101 for(int i = 1;i <= n;++i)//初始化标记数组102 dist[i] = maxint;//该数组记录从起点到该点的最短路径长度103104105 dijkstra(n,1,dist,prev,c);106 printf("从源点到最后一个顶点的最短路径长度为：%d\n",dist[n]);107 printf("从源点到最后一个顶点的路径为：");108 searchpath(prev,1,n);109}全局最短路求图中所有的最短路径。
最短路问题的三种算法模板最短路算法&模板最短路问题是图论的基础问题。
本篇随笔就图论中最短路问题进⾏剖析，讲解常⽤的三种最短路算法：Floyd算法、Dijkstra算法及SPFA算法，并给出三种算法的模板。
流畅阅读本篇博客需要有图论的基础知识，了解什么是图，什么是最短路，以及⼀些基本语法知识和算法基础。
1、Floyd算法我个⼈认为，Floyd算法是三种最短路算法中最简单、最好理解的算法。
它的适⽤范围是任意两点之间的最短路。
这⼀点是其他两种算法（单源最短路）⽆法⽐拟的。
它的实现思路也很简单：⽤三重循环，枚举断点、起始点和终点（注意：顺序千万不能反！！），如果起始点到断点，断点到终点的距离和⼩于起始点到终点当前状态下的最短路（也就是说找到了⼀个⽐它还短的），那么就更新最短路。
它的优点就是简洁明了，易于理解，但是缺点也显⽽易见，通过它的实现途径，我们可以发现，使⽤Floyd算法的题⼀定要⽤邻接矩阵存图，这样的⼀个⼆维数组显然对空间有着要求，⼀般来讲，只能⽀持不超过500个点的图，假如更多，便⽆法⽀持。
同时，Floyd算法还对时间有着要求，因为是三重循环，所以它的时间复杂度是O(n3)的，这样的复杂度如果出现在⼀个复杂程序中，极其容易TLE，所以，请⼤家使⽤的时候，⼀定要读题读题，慎重慎重！模板：void Floyd(){memset(map,0x3f,sizeof(map));for(int i=1;i<=n;i++)map[i][i]=0;for(int k=1;k<=n;k++)//顺序不要反for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)map[i][j]=min(map[i][k]+map[k][j],map[i][j]);}2、Dijkstra算法Dijkstra算法，中⽂名是迪杰斯特拉算法，简写是DIJ算法。
DIJ算法是求解单源最短路，即从某⼀个源点到达其他所有点的最短路的⼀个经典算法。
最短路算法题最短路算法是用于解决图论中一类重要问题的算法，即寻找图中从一个顶点到另一个顶点的最短路径。
这里的最短路径可以是路径的长度（边的数量）或路径的权重之和（边的权重）。
以下是一些常见的最短路算法题目类型及其解法：1.单源最短路问题：给定一个图和一个起点，找到从起点到图中所有其他点的最短路径。
2.Dijkstra算法：适用于带权重的图，且权重非负。
该算法每次迭代都会选取当前距离起点最近的一个顶点，并更新该顶点与起点的最短距离。
所有顶点都被访问后，算法结束。
3.Bellman-Ford算法：适用于带权重的图，权重可以为负。
该算法通过对图中的所有边进行迭代松弛操作来找到最短路径。
此外，它还可以检测并处理负权重环。
4.Floyd-Warshall算法：适用于所有顶点对之间的最短路径问题。
它使用动态规划的思想，逐步构建中间点集合，并利用中间点来更新最短路径。
5.多源最短路问题：给定一个图和多个起点，找到从这些起点到图中所有其他点的最短路径。
一种常见的解决方法是对每个起点分别运行单源最短路算法。
但这种方法可能不够高效，特别是当起点数量较大时。
另一种方法是使用更高级的数据结构或算法，如优先队列优化的Dijkstra算法或基于矩阵乘法的Floyd-Warshall算法变种。
5.特定条件下的最短路问题：除了基本的最短路问题外，还有一些特定条件下的最短路问题，如有向无环图（DAG）中的最短路径、边权重受限制的最短路径等。
这些问题通常需要结合特定的图论知识和技巧来解决。
6.在解决最短路问题时，需要注意以下几点：确保理解问题的具体要求，如路径的长度是按边的数量还是按边的权重计算。
根据问题的特点选择合适的算法和数据结构。
例如，对于稠密图，邻接矩阵可能是更好的选择；而对于稀疏图，邻接表可能更合适。
注意处理特殊情况，如负权重环、不连通图等。
这些情况可能导致最短路径不存在或无穷大。
在实现算法时，注意优化性能和减少不必要的计算。
