每对结点间的最短路径
Floyd-Warshall算法:
前提:可以有负权边,但不能有负权回路
时间复杂度: O(V^3)
思路:动态规划/子问题结构/递归
http://chuanwang66.iteye.com/admin/blogs/1439730/edit
例子:Silver Cow Party --> http://poj.org/problem?id=3268
理论上这个题可以用Floyd求解,C++和java代码分别如下。但是时间复杂度会超出。分析可知,Floyd算法为O(V^3),当V比较小的时候,就不如用单源最短路径的方法解决。例如,本题目中,
V=1000, 10^6对应1s钟 ! 而题目要求2s内跑完。
(1)BellmanFord: O(VE) --当用权值矩阵表示图时(通常是这么做的)-->O(V^3)
∴T=O(V^4)=10^12 ==> 10^6秒
(2)Dijkstra: O(V^2) ——普通数组实现优先队列
O((V+E)lgV) ——最小二叉堆实现优先队列
O(VlgV+E) ——斐波那契堆实现优先队列
∴如果使用最小二叉堆实现优先队列的方法, 则T=O(VlgV)*O(V)=O(V^2lgV)=10^6 * 0.3<10^6 ==> 1秒
(3)Floyd: O(V^3)
∴T=O(V^3)=10^9 ==> 1000秒
Java代码-Floyd:
package poj3268;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
* 每对顶点间最短距离——Floyd-Warshall算法
* 注意:下标从1开始算起
*/
public class Main {
private static int N; //farms #
private static int M; //roads #
private static int X; //target farm
private static int w[][];//有向加权图
private static int d[][];//最短路径
private static void Floyd(){
/*
* 所有结点的编号依次为1,2, ... ,N
* 对任意i,j,依次i~~>j的最短路径的中间节点是:(k=1, ... ,N)
* ; (没有中间节点)
* 1;
* 1,2;
* ...
* 1,2,...,N-1
*/
for(int k=1;k<=N;k++){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
//System.out.println("here");
}
}
}
}
}
public static void main(String[] args) {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int maxLen=0;
try {
String[] data=br.readLine().split(" ");
N=Integer.parseInt(data[0]);
M=Integer.parseInt(data[1]);
X=Integer.parseInt(data[2]);
/*
* 初始化
*/
w=new int[N+1][N+1];
d=new int[N+1][N+1];
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(i==j){
d[i][j]=w[i][j]=0;
}
else{
d[i][j]=w[i][j]=Integer.MAX_VALUE/2;
}
}
}
while(M>0){
data=br.readLine().split(" ");
d[Integer.parseInt(data[0])][Integer.parseInt(data[1])]
=w[Integer.parseInt(data[0])][Integer.parseInt(data[1])]
=Integer.parseInt(data[2]);
M--;
}
Floyd();
maxLen=d[1][X]+d[X][1];
for(int i=2;i<=N;i++){
if(d[i][X]+d[X][i]>maxLen)
maxLen=d[i][X]+d[X][i];
}
System.out.println(maxLen);
} catch (IOException e) {
}
}
}
C++代码-Floyd:
#include<iostream>
using namespace std;
const int MAX=999999;
int N,M,X;
int w[1100][1100];//C++在ACM时二维数组一般直接指定固定大小
int d[1100][110];
void Floyd(){
int k,i,j;
for(k=1;k<=N;k++){
for(i=1;i<=N;i++){
for(j=1;j<=N;j++){
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
//System.out.println("here");
}
}
}
}
}
int main()
{
while(scanf("%d%d%d",&N,&M,&X)){
memset(w,MAX,sizeof(w));
memset(d,MAX,sizeof(d));
for(int i=1;i<=N;i++)
d[i][i]=w[i][i]=0;
while(M>0){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
d[a][b]=c;
M--;
}
Floyd();
int maxLen=d[1][X]+d[X][1];
int i;
for(i=2;i<=N;i++){
if(d[i][X]+d[X][i]>maxLen)
maxLen=d[i][X]+d[X][i];
}
printf("%d",maxLen);
}
}
(4)观察代码,发现不用算出两两顶点之间的最短路径,因此,算法可以更加简单。只需计算1个“单源点最短距离” 和 1个“单汇点最短距离”,而后者通过求转置图的“单源点最短距离”即可得到。
注意:这个问题中没有涉及最短路径树;如果涉及,初始时要将所有顶点i的前驱设置为源点s(即p[i]=s),而不能是-1。为什么呢?
因为如果w[s][i]=0,则开始的时候dist[i]就达到最短,因此不会松弛,因此不会更新前驱p[i]=s,而是保持p[i]=-1。这样一来,就不是一棵前驱树了,而是一个森林了:X
关于这一点,可以看看POJ1122
Dij+普通数组==>Accepted
#include<iostream>
using namespace std;
#define CLR(a) memset(a,0,sizeof(a))
const int INF=1<<29;
const int MAX=1005;
//图信息
int n;//有向图顶点数
int m;//有向图边数
int x;//源点
int map[MAX][MAX];//带权有向图
//最短路径信息
int vis[MAX];//是否加入“集合S(已经找到最短路路径的顶点)”
int dis[MAX];//单源最短路径
int sum[MAX];//sum[i]: 从i到源点x+从源点x回i 的路径长度
//初始化图信息
void init(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=(i==j)?0:INF;
}
//转置图
void reversal(){
int i,j;
for(i = 1; i <= n; i++)
for(j = 1; j < i; j++)
map[i][j] ^= map[j][i] ^= map[i][j] ^= map[j][i]; //交换map[i][j] <-> map[j][i]
}
void dijkstra(){
//Dijkstra初始化
CLR(vis);
int i;
for(i=1;i<=n;i++){
dis[i]=map[x][i];
}
//从根(源点)向外发散,开始构造最短路径树
vis[x]=1;
int next=x;//下一个加入“集合S”的顶点
int time=n-1;
while(time--){
int min=INF;//下一个加入“集合S”的顶点距离S的距离
int j;
for(j=1;j<=n;j++){
if(vis[j]==0 && dis[j]<min){
min=dis[j];
next=j;
}
}
//next顶点马上要加入S,说明他已经抵达最短路径状态dis[next]
vis[next]=1;
sum[next]+=min;
//松弛邻接出边
for(j=1;j<=n;j++){
if(map[next][j]<INF && vis[j]==0 && dis[next]+map[next][j]<dis[j]) //*不要忘了map[next][j]<INF
dis[j]=dis[next]+map[next][j];
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&x);
init();
while(m--){
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
if(t<map[a][b])
map[a][b]=t;
}
dijkstra(); //从x回各顶点的最短路径
reversal();
dijkstra();//从各顶点去x的最短路径
int maxdis=0;
int i;
for(i=1;i<=n;i++){
maxdis=max(maxdis,sum[i]);
}
printf("%d\n",maxdis);
system("pause");
return 0;
}
上面代码用“普通数组实现Dijkstra”,可以换成用“最小堆实现Dijkstra”
但下面代码会WA—— ∵stl中的priority_queue不会因为堆中元素改变而自动调整堆,只有在push的时才会调整堆。因此,一般有两种做法:
A. 自己手写一个最小堆,提供维护堆的函数;(推荐)
B. node(pos,dis)中的dis改变后,调用priority_queue.push(*new node(pos,dis_new));但这样做只解决Dij的问题,不通用.(有空补充,参考http://www.cplusplus.com/reference/algorithm/make_heap/)
Dij+MinHeap(stl: priority_queue实现)==>Wrong Answer
#include<iostream>
#include<queue>
using namespace std;
const int MAX=1005;
const int INF=999999;
//图信息
int n;
int w[MAX][MAX];
//最短路径信息
int x;//源点
int dist[MAX];
bool flag[MAX];//Dijkstra算法中是否已经加入集合S;已经找到最短路径的顶点集合
int sum[MAX];//sum[i]: i到x的最短路径长度 + x到i的最短路径长度
//最小堆信息
struct node{
int i;//顶点编号
node(int i){
this->i=i;
}
};
bool operator<(const node &a,const node &b){
return dist[a.i]>dist[b.i];
}
priority_queue<node> minHeap;
void init(){
int i;
for(i=1;i<=n;i++){
memset(w[i],INF,sizeof(w[i]));
w[i][i]=0;
}
/*for test
int e,r;
for(e=1;e<=n;e++){
for(r=1;r<=n;r++){
printf("%d,",w[e][r]);
}
printf("\n");
}
*/
}
void reversal(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<i;j++){
int temp=w[i][j];
w[i][j]=w[j][i];
w[j][i]=temp;
}
}
}
void dijkstra(){
int i;
for(i=1;i<=n;i++){
dist[i]=w[x][i];
}
memset(flag,false,sizeof(flag));
//不要忘了下面这个:
for(i=1;i<=n;i++){
minHeap.push(*new node(i));
}
while(minHeap.empty()==false){
//1. 最小元素弹出最小堆
int next=minHeap.top().i;
minHeap.pop();
//2. 设置相关域
flag[next]=true;
sum[next]+=dist[next];
//3. 更新邻接出边
int i;
for(i=1;i<=n;i++){
if(w[next][i]<INF && flag[i]==false && dist[next]+w[next][i]<dist[i])
dist[i]=dist[next]+w[next][i];
}
}
}
int main(void){
int m;
scanf("%d%d%d",&n,&m,&x);
init();
while(m--){
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
if(t<w[a][b])
w[a][b]=t;
}
dijkstra();
reversal();
dijkstra();
//打印sum[]中最大值
int maxLen=-1;
int i;
for(i=1;i<=n;i++)
if(sum[i]>maxLen)
maxLen=sum[i];
printf("%d",maxLen);
system("pause");
return 0;
}
Dij+MinHeap(手写)==>Accepted
/*
使用最小堆的*心得:
一、stl要实现最小堆:
#include<queue>
struct node{
...
}
bool operator<(const node &a,const node &b){
return ...
}
priority_queue<node>minHeap; //默认弹出大者
但stl中的堆有个缺陷:当非堆顶元素的值改变时不能自动调整堆。
只在minHeap.push()和minHeap.pop()时,即操作堆顶时,才调整堆。
二、自己实现的堆:
1. 堆中指保存“标识信息”(因此只需一个int[]即可);
2. 具体对每个元素的比较可以在堆外面开辟数组
*/
#include<iostream>
#include<queue>
using namespace std;
const int MAX=1100;
const int INF=1<<29;
//图信息
int n;
int w[MAX][MAX];
//最短路径信息
int x; //源点
int dist[MAX]; //Dijkstra单源最短路径
bool flag[MAX]; //Dijkstra算法中是否已经加入集合S;已经找到最短路径的顶点集合
int sum[MAX]; //sum[i]: i到x的最短路径长度 + x到i的最短路径长度
class MinHeap{
private:
int data[MAX]; //堆中元素。只保存顶点位置信息,如需要获取距离,查询dist[i]
int num; //堆的大小
void swap(int a,int b){
int temp=data[a];
data[a]=data[b];
data[b]=temp;
}
//从堆中的某个树根(offset=1开始)到堆底调整堆,每次将三个顶点中最小的一个移上来
void moveDown(int pos){
int first=pos;
int smallest=2*first;
while(smallest<=num){
if(smallest+1<=num && dist[data[smallest+1]]<dist[data[smallest]])
smallest++;
if(dist[data[smallest]]<dist[data[first]]){
swap(smallest,first);
first=smallest;
smallest=smallest*2;
}else
break;
}
}
public:
//找到值为value的第一个元素在堆中的位置
int findHeapPos(int value){
int pos;
for(pos=1;pos<=num;pos++)
if(data[pos]==value)
return pos;
return -1;
}
void showHeap(){
int i;
for(i=1;i<=num;i++){
printf("%d\t",data[i]);
}
if(num==0) printf("empty");
printf("\n");
}
//压入最小堆
void push(int e){
data[++num]=e;
moveUp(num);
}
//查看最小堆顶
int top(){
int rt=-1;
if(num>0){
rt=data[1];
}
return rt;
}
//弹出最小堆堆顶
void pop(){
if(num>0){
data[1]=data[num];
num--;
moveDown(1);
}
}
bool empty(){
return num==0;
}
//当最小堆中非堆顶元素改变(变小)时,从这点开始向上调整堆
//(caution:pos是data[]的下标,不是data[]的值)
void moveUp(int pos){
while(pos>1 && dist[data[pos]]<dist[data[pos/2]]){
swap(pos,pos/2);
pos=pos/2;
}
}
};
MinHeap minHeap;
void reversal(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<i;j++){
int temp=w[i][j];
w[i][j]=w[j][i];
w[j][i]=temp;
}
}
}
void dijkstra(){
int i;
for(i=1;i<=n;i++){
dist[i]=w[x][i];
}
memset(flag,false,sizeof(flag));
//不要忘了下面这个:
for(i=1;i<=n;i++){
minHeap.push(i);
}
while(minHeap.empty()==false){
//1. 最小元素弹出最小堆
int next=minHeap.top();
minHeap.pop();
//2. 设置相关域
flag[next]=true;
sum[next]+=dist[next];
//3. 更新邻接出边
int i;
for(i=1;i<=n;i++){
if(w[next][i]<INF && flag[i]==false && dist[next]+w[next][i]<dist[i]){
dist[i]=dist[next]+w[next][i];
//1. 就这一个地方,对stl中的最小堆做了人性化的改造:)
//2. 最小堆中元素的值是顶点编号,因此这里的i是堆中元素的值(data[j]=i);
// 而调整堆moveUp(j)的参数是data的下标(j)!
minHeap.moveUp(minHeap.findHeapPos(i));
}
}
}
}
int main(void){
int m;
scanf("%d%d%d",&n,&m,&x);
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
w[i][j]=(i==j?0:INF); //不能乱用memset() %>_<%
}
}
while(m--){
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
if(t<w[a][b])
w[a][b]=t;
}
dijkstra();
reversal();
dijkstra();
//打印sum[]中最大值
int maxdis=-1;
for(i=1;i<=n;i++){
if(sum[i]>maxdis)
maxdis=sum[i];
}
printf("%d",maxdis);
system("pause");
return 0;
}
性能比较:
Dij+普通数组: 4108K 79MS
Dij+MinHeap(手写实现): 4480K 32MS 空间费一点,时间少一点