http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591533.html
http://www.cnblogs.com/Yan-C/p/3916281.html
单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。
全源最短路径定义为，找出连接图中各对顶点的最短路径。求解全源最短路径的算法主要有Floyd算法和Johonson算法，其中Floyd算法可以检测图中的负环并可以解决不包括负环的图中的全源最短路径问题；Johonson算法同样也是解决不包含负环的图的全源最短路径问题，但是其算法效率更高。
待补充：
使用C++ vector邻接表的Dijkstra算法模板。
Bellman-Ford的优化：SPFA算法-->虫洞问题。
BFS求解最短路径。
暂时先使用邻接矩阵表示图，用for循环进行寻找最小值操作。
优化时可以考虑邻接表和优先队列。
Dijkstra （贪心）
Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为正值。
该算法可以用优先队列进行优化。
（1）核心算法
以下实现的时间复杂度为O(|V|^2)
int G[203][203];//二维数组 图的存储
int n, s, t;//n 点的个数 , s 起点 ,t 终点
void dijkstra()
{
bool vis[203];//相当于集合Q的功能， 标记该点是否访问过
int dis[203];//保存最短路径
int i, j, k;
for(i=0;i<n;i++) {//初始化
dis[i] = G[s][i];//s—>各个点的距离
//if(i!=s && G[s][i] != INF) pre[i] = s;
//else pre[i] = -1;
}
memset(vis,false,sizeof(vis));//初始化为假 表示未访问过
dis[s] = 0;//s->s 距离为0
vis[s] = true;//s点访问过了，标记为真
for(i=1;i<n;i++)//G.V-1次操作+上面对s的访问 = G.V次操作
{
k = -1;
for(j=0;j<n;j++)//从尚未访问过的点中选一个距离最小的点
if(!vis[j] && (k==-1||dis[k]>dis[j]))//未访问过 && 是距离最小的
k = j;
if(k == -1)//若图是不连通的则提前结束
break;//跳出循环
vis[k] = true;//将k点标记为访问过了
for(j=0;j<n;j++)//松弛操作
if(!vis[j] && dis[j]>dis[k]+G[k][j]) {//该点为访问过 && 可以进行松弛
dis[j] = dis[k]+G[k][j];//j点的距离 大于当前点的距离+w(k,j) 则松弛成功，进行更新
//pre[j] = k;
}
}
printf("%d\n",dis[t]==MAX?-1:dis[t]);//输出结果
}
（2）判断有环
似乎不能？
（3）输出路径
通过pre数组从target输出路径。
（4）Dijkstra优化
//pair 的first 保存的为最短距离, second保存的为顶点编号
typedef pair<int, int >P;//对组 不知道请自行百度
struct node
{
int v, w;//v 为到达的点, w为权重
int next;//记录下一个结构体的位置 ，就向链表的next功能是一样的
};
node edge[2003];//存所有的边，因为是无向图，所以*2
int cnt;//结构体的下标
int n, s, t;//n 点数,s 起点,t止点
int head[203];//和链表的头指针数组是一样的。只不过此处head[u]记录的为最后加入 edge 的且与u相连的边在 edge 中的位置，即下标
void add(int u, int v, int w)//加边操作
{
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];//获得下一个结构体的位置
head[u] = cnt++;//记录头指针的下标
}
void dijkstra()
{
int dis[203];//最短路径数组
int i, v;//v保存从队列中取出的数的第二个数 也就是顶点的编号
priority_queue<P,vector<P>,greater<P> >que;//优先队列 从小到大
node e;//保存边的信息，为了书写方便
P p;//保存从队列取出的数值
fill(dis,dis+n,MAX);//初始化，都为无穷大
dis[s] = 0;//s—>s 距离为0
que.push(P(0,s));//放入距离 为0 点为s
while(!que.empty()){
p = que.top();//取出队列中最短距离最小的对组
que.pop();//删除
v = p.second;//获得最短距离最小的顶点编号
if(dis[v] < p.first)//若取出的不是最短距离
continue;//则进行下一次循环
for(i=head[v];i!=-1;i=edge[i].next)//对与此点相连的所有的点进行遍历
{
e = edge[i];//为了书写的方便。
if(dis[e.v]>dis[v]+e.w){//进行松弛
dis[e.v]=dis[v]+e.w;//松弛成功
que.push(P(dis[e.v],e.v));//讲找到的松弛成功的距离 和顶点放入队列
}
}
}
printf("%d\n",dis[t]==MAX?-1:dis[t]);//输出结果
}
int main()
{
int m, u, v, w;
while(scanf("%d %d",&n,&m)==2){//获取点数 边数
cnt = 0;//结构体下标从0开始
memset(head,-1,sizeof(head));//初始化head[N]数组
while(m--){
scanf("%d %d %d",&u,&v,&w);//获取u,v,w(u,v)
add(u,v,w);//加边
add(v,u,w);//加边
}
scanf("%d %d",&s,&t);//获取起止点
dijkstra();
}
return 0;
}
Bellman-Ford
Bellman-Ford算法诞生于20世纪50年代，对于不包含负环的图，该算法可以简单有效地求解图的单源最短路径问题。算法的基本思路非常简单：以任意顺序考虑图的边，沿着各条边进行松弛操作，重复操作|V|次(|V|表示图中顶点的个数)。
http://blog.csdn.net/xu3737284/article/details/8973615
（1）核心算法
代码来自http://blog.csdn.net/hsqlsd/article/details/7826319
O(VE)
struct Edge
{
int s,e;
int cost;
};
Edge edge[MAX];
int map[505][505];
int n,m,w;
int dist[MAX];
int edge_num;
bool bellman_ford()
{
int s,e,w,i,j;
bool flag;
for(i=1;i<=n;i++)
dist[i] = INF;
dist[1]=0;
for(i=1;i<=n;i++) //顶点下标从1开始,进行dist数组更新操作
{
flag=false;
for (j=0;j<edge_num;j++)
{
s=edge[j].s;
e=edge[j].e;
w=edge[j].cost;
if(dist[e]>dist[s]+w) //松弛迭代过程
{
dist[e]=dist[s]+w;
flag=true;
}
}
if(!flag)
break;
}
}
（2）判断有环
http://www.tuicool.com/articles/YJzyee
struct node
{
int u, v, w;//u 为起点，v为终点，w为u—>v的权值
};
node edge[5203];
int n, m;//n 点数 m 边数
bool bellman_ford()
{
int i, j;
bool flag;
int dis[503];//保存最短路径
fill(dis,dis+n,MAX);//初始化
dis[1] = 0;//因为判断是否有负环，对整个图而言，So s = 1;
//一下部分为 2) 第2~4行的操作
for(i=1;i<n;i++)//共需进行|V|-1次
{
flag = false;//优化 初始化为假
for(j=0;j<m;j++)//对每一条边
{
// if u.d>v.d+w(u,v) , u.d = v.d+w(u,v);
if(dis[edge[j].u]>dis[edge[j].v]+edge[j].w){//进行松弛
dis[edge[j].u] = dis[edge[j].v]+edge[j].w;//松弛操作成功
flag = true;//松弛成功变为真
}
}
if(!flag)//若每条边没有松弛
break;//跳出循环
}
// 一下部分为 3) 第5~8行的操作
for(i=0;i<m;i++)
if(dis[edge[i].u]>dis[edge[i].v]+edge[i].w)//进行|V|-1次操作后 有边还能进行松弛 说明
return true;//存在负环
return false;//不存在负环
}
（3）输出路径
Floyd-warshall（DP）
http://www.cppblog.com/wing/archive/2011/03/10/141511.html
（1）核心算法：
初始化，map[i][i] = 0;不可达=INF;
时间复杂度O(|V|^3)
void floyd(){
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dist[i][j]=map[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
if(dist[i][k] != INF && dist[i][k] != INF
&& dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}
}
（2）判断是否有负环
对于floyd判断负环是否存在只需检查是否存在d[i][i]是负数的顶点i即可。
（3）输出路径
path[][]={} //初始化为0
//if内同时进行以下两个操作
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
//输出函数的用法
cout<<"start ";
output(start, end);
//输出函数
void output(int i,int j){
if(i==j) return;
if(path[i][j]==0) cout<<j<<' ';
else{
output(i,path[i][j]);
output(path[i][j],j);
}
}
网友评论