每对结点间的最短路径

chuanwang66

浏览: 532420 次
性别:
来自: 上海

最近访客更多访客>>

fortunely

yhtppp

lp19911126

林祥纤

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

数据结构和算法

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 空间费一点，时间少一点