大家好，又见面了，我是你们的朋友全栈君。

最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。当然这只是最基础的应用，关于单源最短路径还有很多变体：

1.单源最短路径

2.单目的地最短路径

3.单节点对最短路径

4.所有节点对最短路径

最短路径定义：

路径p=<v0, v1, … vk>的权是指组成p的所有边的权值之和

从u到v的最短路径的权为

从u到v的最短路径是权的任何路径

需要说明的是这里讨论的单源最短路径允许出现负数权值，但是不能图中不能出现权值为负数的环路，因为一旦图中出现了权值为负数的环路那么图中有些节点是不可能有最路径的。例如：图中节点0到节点1权值为1，节点1到节点0权值为-2，那么第一轮从0->1的最短路径为1，但是在节点1的时候发现1->0可以更小也就是-2，下一轮-2+1<1那么节点1的权值被更新为-1，如此循环下去会变成负无穷大。

常用的单源最短路径的解法有两种：Dijkstra算法和bellman_ford算法。

松弛操作

bellman_ford算法

bellman_ford算法可以解决带有负权值的图的单源最短路径，如果图中包含了一个权值为负的环路，则该算法返回false，否则返回true；

初始化

初始化很好理解，就是将图G中的所有节点到源结点s的距离设置为∞表示不可达,而且将所有节点的父节点设置为null,当然s除外

init(G,s){

    foreach  vertex u∈G.V
                u.d=∞
                u.π=null
    s.d=0;
}

核心思想

对每一条边都进行V次松弛操作。或者换一种说法：每次都将所有的边进行松弛，一共持续V次。

这里可以做一个简单的证明为什么这样操作可以得到最短路径；证明之前大家需要先知道一个定理：最短路径中不可能包含环路，如果环路为负那么最终得不到最短路，该算法也会返回false，如果环路为正，那么去掉这个环路一定可以比当前方案更优，而如果环路为0，那么可以直接不用这个环路。有了这个定理，我们可以很简单的推出在含有V个节点的图中，u到v的最短路径最多可以包含V-1条边。我们的算法是每次都对所有的边进行松弛，那么经过V-1次的松弛之后一定可以得到最短路径，当然如果不存在负值环路的话，当松弛的次数大于V-1的时候，各个节点到源结点s的最短距离不会再改变，因为在V-1次的时候已经达到最优。

算法伪代码：

Bellman_Ford(G,w,s){

        init(G,s);
for i=1 to |G.V| – 1
  for each edge(u,v)∈G.E
relax(u,v,w)
for each edge(u,v)∈G.E
if v.d>u.d+w(u,v)//只有存在负值环路的时候该条件才会被满足
return false
return true
}

实例分析

举一个实例手动模拟一下上面的算法，下图中的a是初始化的状态，b是第1次对所有边进行松弛的结果，c是第2次对所有边进行松弛的结果，d是第3次对所有边进行松弛的结果，e是第4次对所有边进行松弛的结果。

第一次松弛的时候可以看到检测t–>x，y–>x,y–>z等都是∞加上某个数字，属于不可改善的情况，只有与s直接相连的t和y是可以改善的，因此第一次松弛只能改善t和y到s的距离。后面的几次都是这样分析这里不再啰嗦。

实现代码（仅作参考）

#include<iostream>
#include<climits>
const int M=100;
using namespace std;
struct vertex{
	int smallCost;
	int father;
}; 
struct edge{
	int start;
	int end;
	int cost;
};
vertex V[M];
edge arr[M];
void init(int v,int s){//v个节点，对v进行初始化,s为起点 
	for(int i=1;i<=v;i++){
		V[i].smallCost=INT_MAX;
		V[i].father=-1;
	}
	V[s].smallCost=0;	
}
bool bell_fold(int v,int e,int s){//时间复杂度为：O(VE) 
	init(v,s);
	for(int i=1;i<=v-1;i++){
		for(int j=1;j<=e;j++){
				int x=arr[j].start;
				int y=arr[j].end;
				int z=arr[j].cost;
				if(V[x].smallCost!=INT_MAX&&V[y].smallCost>V[x].smallCost+z){
					V[y].smallCost=V[x].smallCost+z;
					V[y].father=x;
				}
		}
	}
	for(int j=1;j<=e;j++){
		int x=arr[j].start;
		int y=arr[j].end;
		int z=arr[j].cost;
		if(V[x].smallCost!=INT_MAX&&V[y].smallCost>V[x].smallCost+z)
			return false;			
	}
	return true;
}
void printPath(int src,int des){
	if(des==src)
		cout<<des;
	else{
		printPath(src,V[des].father);
		cout<<"-->"<<des;
	}
	
}
int main(){
	int v,e,s;//v个顶点e条边 s为起始点
	cin>>v>>e>>s;
	for(int i=1;i<=e;i++)
		cin>>arr[i].start>>arr[i].end>>arr[i].cost;
	bell_fold(v,e,s);
	for(int i=1;i<=v;i++){
		cout<<"from "<<s<<" to "<<i<<" smallest cost:"<<V[i].smallCost<<".path:";
		printPath(s,i);
		cout<<endl;	
	}
	
	return 0;
}
/* 
5 10 1
1 2 6
1 5 7
2 5 8
2 3 5
3 2 -2
4 1 2
4 3 7
2 4 -4
5 3 -3
5 4 9
*/

时间复杂度

        该算法的时间复杂度很好分析，对每一条边都进行V次的松弛，因此该算法的时间复杂度为O(VE)，对于稀疏图而言的话效率还算不错，但是对于稠密图（E≈V^2），效率不是很高，因为稠密图的时候O(VE)≈O(V^3)。整体而言效率并不是特别高。一般而言，算法效率不高是因为大量的重复操作，下面我们来分析一下都有哪些重复操作。我们在进行实例分析的时候会发现，如果有很多个节点，而且有很多条边的话，在前几次的松弛中会做很多无用操作，因为都是∞不能松弛，而在最后几次松弛中前面已经有很多节点是达到了最优，所以也不能进行松弛，这些无用的重复操作是造成算法效率不高的主要原因。

dijkstra算法

核心思想

算法步骤：

引入一个辅助数组d。它的每一个分量d[i]表示目前为止找到的从源点v0到终点vi 的最短路径的长度。

初始状态：
若从源点v0到顶点vi有边，则d[i]为该边上的权值；
若从源点v0到顶点vi 没有边，则d[i]为+∞。
把源点v0加入集合S。

算法步骤：
1.找出V- S 中距离源点最近的顶点k，将其加入S：
  d[k] ← min{d[i]}; 
         S ← S ∪ { k };
 2.修改V- S 中，与刚刚加入的顶点k相邻接的顶点的对应属性d：  
        for each i ∈ V- S ,  and <k,i>∈E 
d[i] ← min{ d[i], d[k] + w(k,i) }; 
3. 判断：  若S = V, 则算法结束，否则转1

实例推导

算法步骤是指导纲要，具体实施还是要看oIer的水平，

代码实现：

变量及其说明，如果不光是求出某两个节点之间的最短路径，要求出最短路径的具体路径，就需要增加一个属性保存前驱节点，因此我将他们直接封装为一个struct，node表示某个节点的信息，father是该节点的直接前驱节点，cost表示该节点到源结点的最短路径值。另外，使用领接链表的形式存储图，因为使用指针太麻烦了，而且容易出错，关键是还需要要自己去分配内存，因此直接使用了vector数组来模拟，以减少实现难度。当然这里同样可以使用list数组模拟，但是那样不能像二维数组一样直接使用双下标取值，要使用迭代器也是比较麻烦的。

struct node{//顶点信息 
	int father;//该节点的直接父节点 
	int cost;//该节点到源结点的最短权值 
}; 
struct edge{//所有边都会加入到数组vector中去，数组下标为该边的起点 
	int dest;//边的结束点的下标 
	int cost;
};
node vertex[M];
bool isVisited[M]={0};//表示某个节点是不是被访问过 
vector<edge> graph[M];//挂链表的形式保存图，因为要修改某个节点领接节点的值，所以必须保存图

初始化

void init(int v,int s){//v个节点，对所有节点初始化,s为起点 
	for(int i=1;i<=v;i++){
		vertex[i].cost=INT_MAX;//所有节点的权值都是∞ 
		vertex[i].father=i;//父节点都是节点本身 
	}
	vertex[s].cost=0;//源结点的权值为0 
}

dijkstra算法框架

void dijkstra(int v,int e,int s){//时间复杂度为：O(V^2+E) 
	init(v,s);//初始化 
	for(int i=1;i<=v;i++){//一共有V个节点，每次取出一个节点，因此一共需要执行V次 
		int u=getMin(v);//取得离源结点最近的节点 
		relax(u);//松弛所有与源结点相邻的节点 
	}
}

获取最小值

取得最小值有两种操作方式，第一种是O(n)复杂度的遍历，第二种是O(1)时间的小根堆，不过小根堆实现比较难，但是删除和建立时间复杂度为lgN比直接遍历效率高；本来最开始准备直接使用stl中的priority_queue，后面发现加入到优先级队列里面的元素的值并不能进行改变，写小根堆又太麻烦了就直接遍历了，如果需要深入学习写高效率的建议使用堆来实现。

int getMin(int v){//获取没有访问过的最小节点 
	int res=INT_MAX;
	int index=-1;
	for(int i=1;i<=v;i++){
		if((isVisited[i]==0)&&(res>=vertex[i].cost)){
			res=vertex[i].cost;
			index=i;
		}
	}
	isVisited[index]=1;
	return index;
}

路径打印

只要知道每个节点的直接前驱节点，那么一定可以得到完整的路径，因为最短路径具有最优子结构的性质。（最优子结构就是如果结果最优，那么过程中得到的过度结果也一定最优）关于最优子结构其实不难证明，假设A——->D的最优结果k是A–>C—>D，并且A–>C的距离为x,C–>D的距离为y,也就是说k=x+y;现在假设A–>C的最优结果是x1而不是x,那么就意味着x1<x，如果上式成立，那么x1+y<x+y一定成立，也就是说A———>D的最优结果不是k这与原假设矛盾。因此如果A——D最优结果途径C那么A—–>C也一定最优。所以我们只需要知道每个节点的前驱节点就一定可以打印一条最短路径出来。

void printPath(int startPoint,int destination){
	if(destination==startPoint)
		cout<<destination;
	else{
		printPath(startPoint,vertex[destination].father);
		cout<<"-->"<<destination;
	}
}

完整代码

#include<iostream>
#include<climits>
#include<vector>
const int M=100;
using namespace std;
struct node{//顶点信息 
	int father;//该节点的直接父节点 
	int cost;//该节点到源结点的最短权值 
}; 
struct edge{//所有边都会加入到数组中去，数组下标为该边的起点 
	int dest;//边的结束点的下标 
	int cost;
};
node vertex[M];
bool isVisited[M]={0};//表示某个节点是不是被访问过 
vector<edge> graph[M];//挂链表的形式保存图，因为要修改某个节点领接节点的值，所以必须保存图 
void printVertex(int v){//输出顶点到源结点的最小距离 
	for(int i=1;i<=v;i++)
	cout<<i<<":"<<vertex[i].cost<<"   "<<vertex[i].father<<endl;
} 
void init(int v,int s){//v个节点，对所有节点初始化,s为起点 
	for(int i=1;i<=v;i++){
		vertex[i].cost=INT_MAX;//所有节点的权值都是∞ 
		vertex[i].father=i;//父节点都是节点本身 
	}
	vertex[s].cost=0;//源结点的权值为0 
}
int getMin(int v){//获取没有访问过的最小节点 
	int res=INT_MAX;
	int index=-1;
	for(int i=1;i<=v;i++){
		if((isVisited[i]==0)&&(res>=vertex[i].cost)){
			res=vertex[i].cost;
			index=i;
		}
	}
	isVisited[index]=1;
	return index;
}
void relax(int u){//对和u相连接的所有节点进行松弛 
	int len=graph[u].size();
	for(int i=0;i<len;i++){
		int des=(graph[u][i]).dest;
		if((vertex[u].cost!=INT_MAX)&&(vertex[des].cost>vertex[u].cost+(graph[u][i]).cost)){
			vertex[des].cost=vertex[u].cost+(graph[u][i]).cost;
			vertex[des].father=u;
		}
	}
}
void dijkstra(int v,int e,int s){//时间复杂度为：O(V^2+E) 
	init(v,s);//初始化 
	for(int i=1;i<=v;i++){//一共有V个节点，每次取出一个节点，因此一共需要执行V次 
		int u=getMin(v);//取得离源结点最近的节点 
		relax(u);//松弛所有与源结点相邻的节点 
	}
}
void printPath(int startPoint,int destination){
	if(destination==startPoint)
		cout<<destination;
	else{
		printPath(startPoint,vertex[destination].father);
		cout<<"-->"<<destination;
	}
}

void printRoad(int v,int s){
	for(int i=1;i<=v;i++){
		cout<<"from "<<s<<" to "<<i<<" smallest cost:"<<vertex[i].cost<<".path:";
		printPath(s,i);
		cout<<endl;	
	}
}
int main(){
	int v,e,s;//v个顶点e条边 s为起始点
	cin>>v>>e>>s;
	int a,b,c;//a到b的花费为c 
	edge temp;
	for(int i=1;i<=e;i++){
		cin>>a>>b>>c;
		temp.dest=b;
		temp.cost=c;
		graph[a].push_back(temp);
	}
	dijkstra(v,e,s);
	printRoad(v,s);
}
/* 
5 10 1
1 2 10
1 5 5
2 5 2
2 3 1
3 4 4
4 1 7
4 3 6
5 2 3
5 3 9
5 4 2
*/

时间复杂度

使用便利的方式来找到最小值的效率偏低，整个算法时间复杂度为O(V^2)，如果使用小根堆算法效率可以达到O(VlgV)，但是高效率跟随者实现难度，因此oIer们一定要在时间，实现难度，效率，得分之间进行平衡。该算法相比于bellman_ford算法减少了不必要的重复操作，但是必须熟记，该算法只能用于权值为正数的情况。