一、最短路径的基本概念
- 无权图：路径包含的边的条数。
- 带权图：路径包含的各边权值之和。
- 长度最小的路径称为最短路径，最短路径的长度也称为最短距离。
二、无权图单源最短路径
无权图单源最短路径使用BFS求出，时间复杂度为O(n+e)。该算法可以求出单源到所有顶点的最短路，并且可以通过静态链表的方式存储各顶点的最短路径信息。
在BFS访问的过程中，当访问某个顶点时，就确定了该点与源点的最短距离。
#include<bits/stdc++.h>
using namespace std;
#define n 10
struct Edge{
int VerName;
Edge * next;
};
struct Vertex{
int VerName;
Edge * edge=nullptr;
};
vector<int> path(n);
Vertex Head[n];
vector<int> dist(n,0x3f3f3f3f);
void BFS(Vertex * Head,int s){
dist[s]=0;path[s]=-1;
queue<int> q;
q.push(s);
while(!q.empty()) {
int pre=q.front();q.pop();
for(Edge * edge=Head[pre].edge;edge!=nullptr;edge=edge->next) {
int k=edge->VerName;
if(dist[k]==0x3f3f3f3f) {//未被访问过
dist[k]=dist[pre]+1;
q.push(k);
path[k]=pre;//记录该路径的前驱
}
}
}
return;
}
int main(void) {return 0;}三、Dijkstra算法（正权图单源）
虽然在关键路径中，我们使用过拓扑排序+动态规划求最长路径，时间复杂度是O(n+e)。但是这是在图存在拓扑排序时才能使用的。一般情况下的图更加复杂。一般情况下的正权图，可以使用迪杰斯特拉算法求出最短路径。迪杰斯特拉不能求带有负权图的最短路径。
Dijkstra算法可以求出单源点到所有点的最短路径。该算法使用优先队列可以优化成O(nlogn)。
1.1、算法的基本步骤
①将图中的所有顶点分成两个集合，一个是集合S，一个是集合V-S，S中的顶点表示已经确定最短路的顶点，V-S中表示尚未确定最短路的顶点。
②在初始时S为空集，将源点压入优先队列，执行③
③在V-S中选择离源点最近的顶点（包括源点自身），将该顶点放入S，表示该顶点已经求出最短路径，执行④
④遍历该顶点的所有边，更新其他顶点的最短路径，重复③，直至所有顶点都已经求出最短路径。
该算法实现时遍历所有顶点一次，遍历所有边一次，对于每一个顶点的所有边访问的顶点只要不在S中都压入优先队列中（延迟出栈，不修改队列中的元素，也可以直接自定义实现修改队列中的元素），可能重复压栈，因此时间复杂度为O(nloge+e)。由于e<=n^2 loge<=2logn，取最大阶，因此时间复杂度为O(nlogn)。
1.2、算法的实现
这里采用STL的优先队列的方法，优先队列采用延迟出栈，出栈的顶点若不在S中，则选择它，如果出栈的顶点在S中，则忽略该顶点，直至找到真正不在S中的顶点，多个副本在优先队列中是没问题的，因为多个副本距离最短的优先出队。
int n=100; vector<int> dist(n,0x3f3f3f3f); vector<int> path(n); void Dijkstra(Vertex * Head,int s){ unordered_set<int> S_set;//集合S priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;//默认是大根堆，定义小根堆! {dist,k} 直接使用pair的比对函数，先比较dist，dist小者优先 q.push({0,s}); dist[s]=0;path[s]=-1; while(S_set.size()!=n&&!q.empty()){//若非全部入S//如果提前空了，则说明s并不能到达所有顶点 while(S_set.find(q.top().second)!=S_set.end()) q.pop();//不能用单纯有没有更新过判断，因为它可能被更新过但不是最小的 if(q.empty()) break; int pre=q.top().second;q.pop(); S_set.insert(pre); for(Edge * edge=Head[pre].edge;edge!=nullptr;edge=edge->next) { int k=edge->VerName; if(S_set.find(k)==S_set.end()){//在S中不需要更新了 dist[k]=min(dist[k],dist[pre]+edge->cost); if(dist[k]==dist[pre]+edge->cost){ path[k]=pre;//更新前驱 q.push({dist[k],k});//只有被更新了才导入，没被更新不是最优解就不导了 } } } } return; }