12.带权有向图中任意两点间的最短路径
其实它的代码理解起来真的挺难的我觉得！！！
昨天看了一下午感觉晦涩难懂，还是matlab好用，直接调用函数就可以了！！！
不过这里还是得跟大家介绍一下：
1.问题的理解：
像这种带权的有向图，每一行都表示该行标号对应列标号的有向权值，本身到本身的数值为0，没办法到达的数值为∞
2.最优子结构
i,j是图里面的两个不同顶点，设p为从i到j的不经过{k+1,k+2,...n}点的最短路径
（1）若p不经过顶点k,则p也是从i到达j其间不经过{k,k+1,k+2...n}的最短路径
（2）若p经过顶点k,我们把前半段从i到k记为p1，后半段从k到j记做p2,则p1是从i到k不经过{k，k+1,...n}的最短路径，p2是从k到j的其间不经过{k,k+1,k+2...n}的最短路径
算法伪代码：
FLOYD-WARSHALL(w)
1. for i<-1 to n
2. do for j<-1 to n
3. do if i=j or w[i,j]=∞
4. then π[i,j]<-NIL
5. else π[i,j]<-i
6. D<-w
7. for k<-1 to n
8. do for i<- 1 to n
9. do for j<-1 to n
10. if D[i,j]>D[i,k]+D[k,j]
11. then D[i,j]<-D[i,k]+D[k,j]
12. π[i,j]<-π[k,j]
13. return D,π
(吐槽一下，这里的D其实就是每行标号到每列标号的最短距离，后期程序出来后还是很漂亮的，然后这里的π我就不知道什么鬼了，索性就不管他啦，哈哈！！)
PRINT-ALL-PAIRS-SHORTEST -PATHS(π,i,j)
1. if i=j
2. then print i
3. else if π[i,j]=NIL
4. then print"no path from " i “to” j "exists"
5. else PRINT-ALL-PAIRS-SHORTEST-PATHS(π,i,π[i,j])
6. print j
C++:
floyd.h
#define _floyd_h
#include<string.h>
#include<float.h>
#include<stdio.h>
#include"pair.h"
#include<malloc.h>
pair floydwarshall(double* w,int n){
double *d=(double*)malloc(n*n*sizeof(double));
int i,j,k,*pi=(int*)malloc(n*n*sizeof(int));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(j==i||w[i*n+j]>=DBL_MAX)
pi[i*n+j]=-1;
else
pi[i*n+j]=i;
memcpy(d,w,n*n*sizeof(double));
for(k=1;k<=n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i*n+j]>d[i*n+k-1]+d[(k-1)*n+j]){
d[i*n+j]=d[i*n+k-1]+d[(k-1)*n+j];
pi[i*n+j]=pi[(k-1)*n+j];
}
return make_pair(d,pi);
}
void printallpairsshotestpath(int *pi,int n,int i,int j){
if(i==j){
printf("%d ",i+1);
return;
}
if(pi[i*n+j]==-1)
printf("no path from %d to %d exists.\n",i+1,j+1);
else{
printallpairsshotestpath(pi,n,i,pi[i*n+j]);
printf("%d ",j+1);
}
}
main.cpp
#include<stdlib.h>
#include"floyd.h"
int main(){
double w[]={0,3,8,DBL_MAX,-4,
DBL_MAX,0,DBL_MAX,1,7,
DBL_MAX,4,0,DBL_MAX,DBL_MAX,
2,DBL_MAX,-5,0,DBL_MAX,
DBL_MAX,DBL_MAX,DBL_MAX,6,0},*d;
int i,j,k,*pi,n=5;
pair r;
r=floydwarshall(w,n);
d=(double*)r.first;
pi=(int*)r.second;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printallpairsshotestpath(pi,n,i,j);
printf(":%1.1f\n",d[i*n+j]);
}
}
free(d);
free(pi);
}
输出结果：
JAVA:
Floyd.java
package Jamin;
import java.util.Arrays;
public class Floyd {
public static Pair floydwarshall(double[][] w) {
int n=w.length,i,j,k;
double[][] d=new double[n][n];
int[][] pi=new int[n][n];
d=Arrays.copyOf(w,n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(j==i||w[i][j]>=Double.MAX_VALUE)
pi[i][j]=-1;
else
pi[i][j]=i;
for(k=1;k<=n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][j]>d[i][k-1]+d[k-1][j]) {
d[i][j]=d[i][k-1]+d[k-1][j];
pi[i][j]=pi[k-1][j];
}
return Pair.make(d, pi);
}
public static void printallpairsshotestpath(int[][] pi,int i,int j) {
int n=pi.length;
if(i==j) {
System.out.print((i+1)+" ");
return;
}
if(pi[i][j]==-1)
System.out.println("no path from " +(i+1)+"to "+(j+1)+"exists.");
else {
printallpairsshotestpath(pi,i,pi[i][j]);
System.out.print((j+1)+" ");
}
}
}
Test.java
package Jamin;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
double[][] w= {{0.0,3.0,8.0,Double.MAX_VALUE,-4.0},
{Double.MAX_VALUE,0.0,Double.MAX_VALUE,1.0,7.0},
{Double.MAX_VALUE,4.0,0.0,Double.MAX_VALUE,Double.MAX_VALUE},
{2.0,Double.MAX_VALUE,-5.0,0.0,Double.MAX_VALUE},
{Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,6.0,0.0}
},d;
int n=5,i,j,k;
int[][] pi;
Pair r;
r=Floyd.floydwarshall(w);
d=(double[][])r.first;
pi=(int[][])r.second;
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
Floyd.printallpairsshotestpath(pi, i, j);
System.out.println(":"+d[i][j]);
}
}
}
}
输出结果跟上面一样的！