最短路
dijkstra：单源点最短路，不能判断负权
比如n=3，邻接矩阵：
0，3，4
3，0，-2
4，-2, 0
用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。
int main()
{
for(int i = 0; i < n; i++)
d[i] = map[x][i];//d[i]表示从源点到各点的距离
vis[x] = 1;//起始点已经加入集合
d[x] = 0;
for(int i = 0; i < n; i++)
{
min = max;
for(int j = 0; j < n; j ++)
{
if(!vis[j]&&min < d[j] )
{
int p = j;
min = d[p];
}
vis[p] = 1;//找距离源点最小的点
for(int j = 0; j < n; j++)
{
if(!vis[j]&&d[j]>min+map[p][j])
d[j] = d[i] + map[p][j];
}//更新这点所连的点
}
}
}
Bellman-Ford：可以判断是否有负权
和dijkstra的区别：不知道每次更新的是哪个点判断负权的方法：先求一次最短路，再进行同样的操作，如果一个点第n次又被更新了，说明存在负环/
struct edge
{
int from;
int to;
int cost;
};
edge e[maxn];//边
int d[maxn] //最短距离
int V,E;//顶点数，边数
int flag = 1;
void Bellman-Ford(int s)
{
for(int i = 0; i < V; i++)
{
d[i] = INF;
}
d[s] = 0;
while(1)
{
flag = 0;
for(int i = 0; i < E; i++)
{
edge ee = e[i];
if(d[ee.from]!= INF&&d[ee.to]>d[ee.from] + ee.cost)
{
d[ee.cost] = d[ee.from] + ee.cost;
}
flag = 1;
}
if(!flag)
break;
}
}//求解源点到所有点的最短距离
bool find_negative_loop
{
memset(d,0,sizeof(d));
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j++)
{
edge ee = e[j];
if(d[ee.from]!= INF&&d[ee.to]>d[ee.from] + ee.cost)
{
d[ee.cost] = d[ee.from] + ee.cost;
if(i == V -1)//如果第n次更新了，则存在负权
return true;
}
}
}
return false;
}
Floyd-Warshall:任意两点间的最短路,可以判断图中是否有负权
判断方法：检查是否存在d[i][j]为负数
i:起点 j：终点 k：顶点
分i到j的最短路正好经过顶点k一次和完全不经过k两种情况
d[i][j] = min(d[i][j],d[i][k]+d[k][j])
int d[maxn][maxn];
int V;
void warshall_floyd
{
for(int k = 0; k < V; k++)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
d[i][j] = min(d[i][j],d[i][k]+ d[k][j]);
}
}
}
}
spfa+链式前向星
SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算,算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队
链式前向星：
void add(int u,int v,int w)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
1 2
2 3
3 4
1 3
4 1
1 5
4 5
edge[0].to = 2; edge[0].next = -1; head[1] = 0;
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
head[i]保存的是以i为起点的所有边中编号最大的那个,而把这个当作顶点i的第一条起始边的位置.
这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性.
比如以上图为例,以节点1为起点的边有3条,它们的编号分别是0,3,5 而head[1] = 5
for(int i=head[u];~i;i=edge[i].next)
那么就是说先遍历编号为5的边,也就是head[1],然后就是edge[5].next,也就是编号3的边,然后继续edge[3].next,也
就是编号0的边,可以看出是逆序的.
spfa：
如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
首先建立起始点a到其余各点的
最短路径表格
首先源点a入队，当队列非空时：
１、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：
在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点
需要入队，此时，队列中新入队了三个结点b,c,d
队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：
在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要
入队，此时队列中的元素为c，d，e
队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：
在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此
e不用入队了，f要入队，此时队列中的元素为d，e，f
队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：
在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g
队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：
在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e
队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：
在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b
队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：
在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b
队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：
在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了
最终a到g的最短路径为１４
bool spfa(){
vis[1] = 1;
queue<int> q;
q.push(1);
d[1] = 0;
bool flag = false;
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = id[t]; ~i; i = e[i].nex){
// printf("u = %d, v = %d, d[%d] = %d, d[%d] = %d, len_uv = %d\n", t, e[i].v, t, d[t], e[i].v, d[e[i].v], e[i].len);
if(d[e[i].v] > d[t] + e[i].len){
d[e[i].v] = d[t] + e[i].len;
// printf("u = %d, v = %d, d[%d] = %d, d[%d] = %d\n", t, e[i].v, t, d[t] ,e[i].v ,d[e[i].v]);
if(!vis[e[i].v]){
vis[e[i].v] = 1;
time[e[i].v]++;
if(time[e[i].v] > n){ flag = true;}
q.push(e[i].v);
}
}
}
vis[t] = 0;
}
http://blog.****.net/zhhe0101/article/details/53871453 线段树
http://blog.****.net/liangzhaoyang1/article/details/51169090 k 最小生成树
http://blog.****.net/xunalove/article/details/70045815 spfa