spfa 就是加了一个剪枝（忽略了不需要考虑的节点）
1.起点加入队列 O(1)
2.取队列中距离起点最近的点i O(1) or O(1) = O(1)
2.1判断i是否为终点 如果是 结束 O(1)
2.2判断i是否值得进一步计算(当前i到起点距离是已知i到起点距离中最小的) O(1) or O(1) = O(1)
2.2.1如果不值得 返回2 O(1)
2.2.2如果值得 记录当前距离为最小距离并继续 O(1)
3.遍历i的相邻节点j。 O(m/n)
3.1判断j是否值得加入队列(当前j到起点距离是已知j到起点距离中最小的) O(log(len(prority_queue)))
3.1.1如果不值得，继续3的遍历 O(1)
3.1.2如果值得加入队列 记录当前距离为最小距离并继续 O(log(len(prority_queue)))
4返回2；
2~3最多执行n次
这不是dijstra+剪枝吗？
难道写错了？
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int max_point = 100100;
struct Node
{
int target;
int dist;
}node,node_t;
struct cmp
{
bool operator ()(Node n1,Node other)
{
return n1.dist>other.dist;
}
};
vector<Node> edge[max_point];
int dis[max_point];
int main()
{
priority_queue<Node,vector<Node>,cmp> pri_que;
int n,m,s,t;
cin>>n>>m>>s>>t;
s--,t--;
memset(dis,0x0f,sizeof(dis));
int v,u,d;
for(int i=0;i<m;i++)
{
cin>>v>>u>>d;
v--,u--;
node.target = u;
node.dist = d;
edge[v].push_back(node);
node.target=v;
edge[u].push_back(node);
}
node.target = s;
node.dist = 0;
pri_que.push(node);
while(true)
{
node = pri_que.top();
pri_que.pop();
if(dis[node.target]<node.dist)
{continue;}
else
dis[node.target] = node.dist;
if(node.target == t)
{
break;
}
for(int i=0;i<edge[node.target].size();i++)
{
int next_tar = edge[node.target][i].target;
int next_dis = edge[node.target][i].dist;
int new_dis = next_dis+node.dist;
if(new_dis>dis[next_tar])
continue;
else{
node_t.target = next_tar;
node_t.dist = new_dis;
dis[next_tar]=new_dis;
pri_que.push(node_t);
}
}
}
cout<<dis[t]<<endl;
return 0;
}
#1093 : 最短路径·三：SPFA算法 hihocoder SPFA
原文：http://www.cnblogs.com/tjsudys/p/5400100.html