立即注册 登录
About云-梭伦科技 返回首页

hyj的个人空间 https://www.aboutyun.com/?2 [收藏] [复制] [分享] [RSS]

日志

java spfa 算法 demo 最短路径双向

已有 838 次阅读2019-5-21 15:47 |系统分类:人工智能

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


public class MySpfa {

public static void main(String[] args) {
MySpfa mySpfa = new MySpfa();
mySpfa.init();
if(!mySpfa.spfa(93)){
System.out.println("出现负环,最短路不存在");
}else{
System.out.println("节点78到节点%d的最短距离为:");
System.out.println(mySpfa.pathMap.toString());
String a = mySpfa.recordMap.toString();
System.out.println(a);
System.out.println(a.split("[,]")[0]);
}

}
//点集合
public int[] V={53,95,94,54,93,96};
// 点边集合
public Map<Integer,NodeEage> edges=new HashMap<Integer,NodeEage>();
//存储到原点0的距离,可以开二维数组存储每对节点之间的距离
HashMap<Integer,Integer> dist = new HashMap<Integer,Integer>(); 
//用于判断该节点是否已经在队列中
HashMap<Integer,Boolean> done = new HashMap<Integer,Boolean>();
//记录入队次数,超过V则退出
HashMap<Integer,Integer> cnt = new HashMap<Integer,Integer>();
// 记录最短路径+值集合
HashMap<String,Integer> recordMap = new HashMap<String,Integer>();
// 记录最短路径集合
HashMap<Integer,String> pathMap = new HashMap<Integer,String>();
// 缓存存储队列
LinkedList  linkList = new LinkedList();
public void init(){
NodeEage n1 = new NodeEage(93);
Eage e1 = new Eage(1,53);
Eage e2 = new Eage(64,95);
n1.listEage.add(e1);
n1.listEage.add(e2);
edges.put(93, n1);
NodeEage n2 = new NodeEage(53);
Eage e3 = new Eage(0,93);
Eage e4 = new Eage(0,94);
n2.listEage.add(e3);
n2.listEage.add(e4);
edges.put(53, n2);
NodeEage n3 = new NodeEage(94);
Eage e5 = new Eage(1,53);
Eage e6 = new Eage(64,96);
n3.listEage.add(e5);
n3.listEage.add(e6);
edges.put(94, n3);
NodeEage n4 = new NodeEage(96);
Eage e7 = new Eage(1,54);
Eage e8 = new Eage(64,94);
n4.listEage.add(e7);
n4.listEage.add(e8);
edges.put(96, n4);
NodeEage n5 = new NodeEage(54);
Eage e9 = new Eage(0,95);
Eage e10 = new Eage(0,96);
n5.listEage.add(e9);
n5.listEage.add(e10);
edges.put(54, n5);
NodeEage n6 = new NodeEage(95);
Eage e11 = new Eage(1,54);
Eage e12 = new Eage(64,93);
n6.listEage.add(e11);
n6.listEage.add(e12);
edges.put(95, n6);
}
boolean spfa(int st){
for(int i=0;i<V.length;i++){ //初始化:将除了原点st的距离外的所有点到st的距离均赋上一个极大值
int tt = V[i];
if(tt==st){
dist.put(st, 0); //原点距离为0;
continue;
}
dist.put(tt, 11111111); //非原点距离无穷大
pathMap.put(tt, ""); // 初始为空
}
linkList.addLast(st);
done.put(st, true); //标记原点已经入队
cnt.put(st, 1); //修改入队次数为1
while(!linkList.isEmpty() ){ //队列非空,需要继续松弛
int tmp= (Integer) linkList.peek();
List record = new ArrayList();
for(int i=0;i<edges.get(tmp).listEage.size();i++){
Eage e= (Eage) edges.get(tmp).listEage.get(i);
int dstID = e.to;
int rouMetic = e.distence;
int old1 = (Integer) dist.get(tmp);
int new1 = (Integer) dist.get(dstID);
String oldPath= pathMap.get(tmp);
if((old1+rouMetic)<new1){
dist.put(dstID, old1+rouMetic);
if(oldPath!=null && !oldPath.equals("")){
pathMap.put(dstID, oldPath+"|"+dstID);
}else{
pathMap.put(dstID, tmp+"|"+dstID);
}
String newPath = pathMap.get(dstID);
record.add(newPath+":"+(old1+rouMetic));
recordMap.put(newPath,old1+rouMetic);
if(!done.containsKey(dstID) ){
linkList.addLast(dstID);
done.put(dstID, true);
int a = 0;
if(cnt.containsKey(dstID)){
a= cnt.get(dstID);
}
cnt.put(dstID, a+1);
int b = cnt.get(dstID);
if(b>V.length){ //已经超过V次,出现负环
while(!linkList.isEmpty() ){
linkList.removeFirst();
}
return false; //返回FALSE
}
}
}
}// end for
//弹出队首节点
linkList.removeFirst();
done.put(tmp, false);//将队首节点标记为未入队
System.out.println(tmp+"="+record);
}

return true;
}
}

class Eage{
int distence; //边权
int to; //连接的点
public Eage(int d,int t) {
distence=d;
to=t;
}
}

class NodeEage{
public int from;
public ArrayList listEage; 
public NodeEage(int f) {
from=f;
listEage = new ArrayList();
}
}

路过

雷人

握手

鲜花

鸡蛋

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 立即注册

关闭

推荐上一条 /2 下一条