(最短路径算法整理)

这一篇博客以一些OJ上的题目为载体，整理一下最短路径算法。会陆续的更新。。。

一、多源最短路算法――floyd算法

floyd算法主要用于求任意两点间的最短路径，也成最短最短路径问题。

核心代码：

/**
 *floyd算法
 */
void floyd() {
	int i, j, k;
	for (k = 1; k <= n; ++k) {//遍历所有的中间点
		for (i = 1; i <= n; ++i) {//遍历所有的起点
			for (j = 1; j <= n; ++j) {//遍历所有的终点
				if (e[i][j] > e[i][k] + e[k][j]) {//如果当前i-->j的距离大于i-->k--->j的距离之和
					e[i][j] = e[i][k] + e[k][j];//更新从i--->j的最短路径
				}
			}
		}
	}
}

时间复杂度:O(N^2）

不能使用的情况：边中含有负权值

例题：

1、WIKIOI 1077 多源最短路

/*
 * 1077.cpp
 *
 *  Created on: 2014年5月23日
 *      Author: pc
 */

#include 
  
   
#include 
   
     using namespace std; const int maxn = 105; int e[maxn][maxn]; int n; const int inf = 99999999; void initial() { int i, j; for (i = 1; i <= n; ++i) { for (j = 1; j <= n; ++j) { if (i == j) { e[i][j] = 0; } else { e[i][j] = inf; } } } } /** *floyd算法 */ void floyd() { int i, j, k; for (k = 1; k <= n; ++k) {//遍历所有的中间点 for (i = 1; i <= n; ++i) {//遍历所有的起点 for (j = 1; j <= n; ++j) {//遍历所有的终点 if (e[i][j] > e[i][k] + e[k][j]) {//如果当前i-->j的距离大于i-->k--->j的距离之和 e[i][j] = e[i][k] + e[k][j];//更新从i--->j的最短路径 } } } } } int main() { while (scanf("%d", &n) != EOF) { initial(); int i, j; for (i = 1; i <= n; ++i) { for (j = 1; j <= n; ++j) { scanf("%d", &e[i][j]); } } floyd(); int q; scanf("%d", &q); while (q--) { int a, b; scanf("%d %d", &a, &b); printf("%d\n", e[a][b]); } } return 0; }