1.dijkstra（堆优化版）精讲
代码：
#include <iostream>
#include <list>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class mycomparison{
public:
bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs){
return lhs.second > rhs.second;
}
};
struct Edge{
int to; // 邻接顶点
int val; // 边的权重
Edge(int t,int w):to(t),val(w){
};
};
int main(){
int n,m,p1,p2,val;
cin >> n >> m;
vector<list<Edge>> grid(n + 1);
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1].push_back(Edge(p2,val));
}
int start = 1;
int end = n;
vector<int> minDist(n + 1,INT_MAX);
vector<bool> visited(n + 1,false);
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pq;
pq.push(pair<int,int>(start,0));
minDist[start] = 0;
while(!pq.empty()){
// 1.选取源点到哪个节点最近且该节点未被访问过
pair<int,int> cur = pq.top();pq.pop();
if(visited[cur.first]) continue;
// 2.将该最近节点进行访问标记
visited[cur.first] = true;
// 3.更新非访问节点到源点的距离
for(Edge edge:grid[cur.first]){ // 遍历cur指向的节点
if(!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]){
minDist[edge.to] = minDist[cur.first] + edge.val;
pq.push(pair<int,int>(edge.to,minDist[edge.to]));
}
}
}
if(minDist[end] == INT_MAX) cout << -1 << endl;
else cout << minDist[end] << endl;
}思路：
思路：其实就是贪心算法，从起点出发，去找和该结点直接相联的结点，加入到以访问的集合中，每次都从这个集合出发，扩大该集合，同时在扩大到过程中，选取距离起点最短的距离更新到minDist数组里。这样我们将全部的结点访问过一次后，就可以找到终点距离起点的最短距离了。（我的上一个博客内容）
这里的实现，只是考虑到了我们可能会面临稀疏矩阵的情况，也就是我们存储的点的数量远远大于边的数量，因此这里选择邻接矩阵来存储更加合理。
这里用到了优先队列的实现，用小顶堆来存储节点，这样就方便我们每次取出相邻节点中距离最近的节点，进行操作。
2.Bellman_ford 算法精讲
代码：
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
int main(){
int n,m,p1,p2,val;
cin >> n >> m;
vector<vector<int>> grid;
// 将所有的边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid.push_back({p1,p2,val});
}
int start = 1;
int end = n;
vector<int> minDist(n + 1,INT_MAX);
minDist[start] = 0;
for(int i = 1; i < n; i++){ // 对所有边 松弛n - 1次
for(vector<int> &side : grid){
int from = side[0];
int to = side[1];
int price = side[2];
if(minDist[from] != INT_MAX && minDist[to] > minDist[from] + price){
minDist[to] = minDist[from] + price;
}
}
}
if(minDist[end] == INT_MAX) cout << "unconnected" << endl;
else cout << minDist[end] << endl;
}思路：上述的dijkstra算法只适合权值不为负时的情况，因为dijkstra利用的是贪心算法，利用了正数只能越加越大这一特性，每次我们选择总和最短的距离作为距离源点的距离。但如果权值为负数时，总和是可以越加越小的，它不舍和走一步算一步的贪心算法，因为即使是当前的最优解，后续也可能遇到一个更小的负数，使得局部最优不能推出整体最优。
而Bellman_ford算法是基于动态规划来的。通过对所有的节点进行松弛n-1次，来得到最后的全局最优。这里的松弛，就是如果有比当前路径更短的路径就对此路径进行替换。
