YEN--K最短路算法(K-Shortest-Path) Java实现
阳福
前段时间要做一个Project，在建模过程中发现要求出一个网络拓扑中的前K条最短路才能进行后续的运算，自己研究了一段时间，实现了java版本的YEN--ksp算法。
Yen's算法是Yen 在1971 年提出的以其名字命名 的Yen 算法。Yen's算法基于偏离路径算法思想，算法原理详见https://en.wikipedia.org/wiki/Yen%27s_algorithm
我自己实现的这个算法比较粗糙，还有不少可以优化的地方，比如第一次Dijkstra(s)的时候可以把路径信息存储起来，以便后续无需计算直接使用，这里我就不实现了。
算法所需的数据采用随机生成的方式，并且将设置YEN_ksp(0,55,50)，即求出Node-0到Node-55的前50条最短路
package lib.utils;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
public class Yen_Ksp {
public static int n=100;//节点数
public static double[][] edges=new double[n][n];
public static double[][] edges_tmp=new double[n][n];
public static ArrayList<Path> ans_path=new ArrayList<>();//K最短路径
public static Map<Path, Boolean> dev_path_sql=new HashMap<Path, Boolean>();//用于查询偏离路径是否重复
public static Queue<Path> dev_path_queue = new PriorityQueue<>();//用于存放偏离路径
public static boolean[] s=new boolean[n];//待扩展的节点集合,false:未扩展
public static int[] prev_node=new int[n];//存放前向节点
public static double[] dist=new double[n];//路径的权重和
public static final double INF=10000000;
public static void Dijkstra(int v0){//v0-> otherNode
for(int i=0;i<n;++i){//初始化
dist[i]=edges_tmp[v0][i];
s[i]=false;
if(i!=v0&&dist[i]<INF) prev_node[i]=v0;
else prev_node[i]=-1;
}
s[v0]=true;
dist[v0]=0;
for(int i=0;i<n-1;++i){//从顶点v0确定n-1条最短路径(n-1个顶点)
double min=INF;
int u=v0;
for(int j=0;j<n;++j){//选择当前集合T中具有最短路径的顶点 u
if(!s[j]&&dist[j]<min){
u=j;
min=dist[j];
}
}
s[u]=true;//将顶点u加入到集合s，表示它的最短路径已求得
for(int k=0;k<n;++k){
if(!s[k]&&edges_tmp[u][k]<INF&&dist[u]+edges_tmp[u][k]<dist[k]){
dist[k]=dist[u]+edges_tmp[u][k];
prev_node[k]=u;
}
}
}
}
//路径信息存储在path数组中(在前向节点集合中前向查找)
public static ArrayList<Integer> getPath(int s,int t){
ArrayList<Integer> v=new ArrayList<>();
if(s==t) return v;
v.add(t);
int tmp=t;
while(tmp!=s){
tmp=prev_node[tmp];//tmp的前向节点
v.add(tmp);
}
Collections.reverse(v);
return v;
}
public static void set_link(ArrayList<Integer> p1,int s_node) {//p1:待检测的path,s_node:p1的末结点
int len=ans_path.size();
int len_p=p1.size();
for(int i=0;i<len;++i) {
ArrayList<Integer> p2=ans_path.get(i).path;
if(len_p>=p2.size()) continue;
boolean flag=true;
for(int j=0;j<len_p;++j) {
if(p1.get(j)!=p2.get(j)) flag=false;;
}
if(flag==false) continue;
//前面的path一样,然后就看扩展结点的了
for(int k=0;k<n;++k) {
if(k!=s_node&&edges[s_node][k]!=INF) {//从s_node扩展结点k
if(k==p2.get(len_p)) {//匹配成功，需将s_node->k 设置为INF
edges_tmp[s_node][k]=INF;
}
}
}
}
}
public static void recover_link(int s_node) {
for(int k=0;k<n;++k) {
edges_tmp[s_node][k]=edges[s_node][k];
}
}
public static void YEN_ksp(int s,int t,int k) {
if(s==t||k<=0) return;
//copy
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
edges_tmp[i][j]=edges[i][j];
}
}
Dijkstra(s);
Path p=new Path(getPath(s, t), dist[t]);//最短路,即迭代路径
while(k-->0) {
if(!ans_path.contains(p)) ans_path.add(p);
else continue;
int len=p.path.size();
ArrayList<Integer> path_tmp=new ArrayList<>();//p的部分迭代路径
for(int i=0;i<len-1;++i) {
path_tmp.add(p.path.get(i));
edges_tmp[p.path.get(i)][p.path.get(i+1)]=INF;
set_link(path_tmp,p.path.get(i));
Dijkstra(s);
edges_tmp[p.path.get(i)][p.path.get(i+1)]=edges[p.path.get(i)][p.path.get(i+1)];
recover_link(p.path.get(i));
if(dist[t]>=INF) continue;//没有路径了
Path pp=new Path(getPath(s,t),dist[t]);//修正后的最短路(偏离路径)
// if(!dev_path_sql.containsKey(pp)) {
// dev_path_queue.add(pp);
// dev_path_sql.put(pp.clone(), true);
// }
if(!dev_path_queue.contains(pp)) {
dev_path_queue.add(pp);
}
}
if(dev_path_queue.isEmpty()) break;
p=dev_path_queue.remove();
//dev_path_sql.remove(p);
}
}
public static void main(String[] args) {
Random r=new Random();
//先生成一个树
edges[0][1]=r.nextDouble()*10+10;
edges[1][0]=r.nextDouble()*10+10;
for(int i=1;i<n;++i) {
edges[i-1][i]=r.nextDouble()*10+10;
edges[i][i-1]=r.nextDouble()*10+10;
}
//在树上添加边
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
if(i==j) continue;
if(edges[i][j]>0) {//已经有边了
//edges[i][j]+=r.nextDouble()*50+50;
;
}else {//没边
if(r.nextDouble()>0) {//0.5的概率生成边
edges[i][j]=r.nextDouble()*100+500;
}else {
edges[i][j]=INF;
}
}
}
}
System.out.println("YEN_ksp start:");
YEN_ksp(0,55,50);//求出结点0到结点55的前50条最短路
int len=ans_path.size();
System.out.println(len);
for(int i=0;i<len;++i) {
int len_p=ans_path.get(i).path.size();
for(int j=0;j<len_p;++j) {
System.out.printf("%d ",ans_path.get(i).path.get(j));
}
System.out.printf("dist: %.3f\n",ans_path.get(i).dist);
}
// Dijkstra(1);
// for(int i=0;i<n;++i) {
// System.out.println(dist[i]);
// }
}
}封装的path.java:
package lib.utils;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Path implements Comparable,Cloneable{
public ArrayList<Integer> path;
double dist;
public Path(ArrayList<Integer> path,double dist){
this.path=path;
this.dist=dist;
}
@Override
public int compareTo(Object o) {
Path p=(Path)o;
if(this.dist>p.dist) return -1;
else if(this.dist==p.dist) return 0;
else return 1;
}
@Override
public int hashCode() {
return path.hashCode()+(int)dist;
}
@Override
public boolean equals(Object obj) {
Path p=(Path)obj;
if(this.dist!=p.dist) return false;
int len1=this.path.size();
int len2=p.path.size();
if(len1!=len2) return false;
for(int i=0;i<len1;++i) {
if(this.path.get(i)!=p.path.get(i)) return false;
}
return true;
}
@Override
protected Path clone(){
Path tmp;
try {
tmp=(Path) super.clone();
}catch(CloneNotSupportedException e) {
throw new RuntimeException("This calss not implement Cloneable");
}
tmp.path=(ArrayList<Integer>)this.path.clone();
tmp.dist=this.dist;
return tmp;
}
// public static void main(String[] args) {
// Map<Path, Boolean> dev_path_sql=new HashMap<Path, Boolean>();
// ArrayList<Integer> v1= new ArrayList<>();
// v1.add(1);
// v1.add(2);
// ArrayList<Integer> v2= new ArrayList<>();
// v2.add(1);
// v2.add(2);
// Path p1=new Path(v1,10);
// Path p2=new Path(v2,10);
// dev_path_sql.put(p1.clone(), true);
// System.out.println(dev_path_sql.containsKey(p2));
// p1.path.add(3);
// System.out.println(dev_path_sql.containsKey(p2));
// dev_path_sql.put(new Path(v2,10), true);
// System.out.println(dev_path_sql.size());
// dev_path_sql.remove(new Path(v2,10));
// System.out.println(dev_path_sql.size());
// }
}
运行结果如下：
YEN_ksp start:
50
0 1 55 dist: 521.530
0 53 54 55 dist: 563.921
0 56 55 dist: 567.054
0 57 56 55 dist: 567.667
0 59 58 57 56 55 dist: 573.120
0 52 53 54 55 dist: 574.652
0 50 51 52 53 54 55 dist: 586.064
0 58 57 56 55 dist: 589.331
0 55 dist: 590.887
0 54 55 dist: 613.887
0 47 48 49 50 51 52 53 54 55 dist: 626.572
0 60 59 58 57 56 55 dist: 644.148
0 49 50 51 52 53 54 55 dist: 649.717
0 51 52 53 54 55 dist: 652.126
0 65 64 63 62 61 60 59 58 57 56 55 dist: 656.914
0 48 49 50 51 52 53 54 55 dist: 676.458
0 63 62 61 60 59 58 57 56 55 dist: 687.190
0 62 61 60 59 58 57 56 55 dist: 688.555
0 61 60 59 58 57 56 55 dist: 689.318
0 44 45 46 47 48 49 50 51 52 53 54 55 dist: 694.788
0 64 63 62 61 60 59 58 57 56 55 dist: 695.797
0 66 65 64 63 62 61 60 59 58 57 56 55 dist: 703.198
0 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 705.473
0 46 47 48 49 50 51 52 53 54 55 dist: 723.243
0 45 46 47 48 49 50 51 52 53 54 55 dist: 734.643
0 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 738.297
0 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 740.333
0 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 749.203
0 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 761.700
0 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 769.119
0 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 780.547
0 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 784.978
0 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 793.785
0 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 800.300
0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 802.399
0 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 810.460
0 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 813.899
0 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 818.640
0 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 829.547
0 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 831.752
0 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 832.565
0 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 836.453
0 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 841.897
0 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 852.720
0 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 867.588
0 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 874.265
0 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 876.927
0 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 880.461
0 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 dist: 884.851
0 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 dist: 886.536
另一个基于链表的实现,详见本人github: https://github.com/xycodec/CodeCraft_2019_public/blob/master/src/main/java/com/huawei/graph/Graph.java#L470
类似资料：