广度优先遍历公交路线寻路算法JAVA实现

破晓 · 发表于 2016-7-4 18:05:12

是算法为测试算法，仅供参考

RoadUtil.java

package com.swift.util;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import com.swift.dao.PointsDaoImpl;
import com.swift.dao.RoadDaoIpml;
import com.swift.util.tree.Node;
/**
* 广度优先遍历
*/
public class RoadUtil {
private static Map<Integer, Node> allNode = null;
/**
* 根据ID获取站点名称
* @param pid
* @return
*/
public static String getNameById(int pid)
{
if(allNode == null)
buildTree();
return allNode.get(pid).name;
}
public static Map<String, Object> findRoad(int start, int end)
{
if(start == end) return null;
Map<String, Object> result = new HashMap<String, Object>();
if(allNode == null)
buildTree();
Node sn = allNode.get(start);
Node en = allNode.get(end);
List<Node> findNodes = new ArrayList<Node>(); // 已遍历节点
List<Node> currentNodes = new ArrayList<Node>(); // 当前到达节点
findNodes.add(sn);
currentNodes.add(sn);
List<HashMap<String, Object>> road = new ArrayList<HashMap<String, Object>>();
HashMap<String, Object> roadItem;
if(findRoadAI(currentNodes, en, findNodes))
{
Node temp = en;
while(temp.parent != null && temp != sn)
{
roadItem = new HashMap<String, Object>();
roadItem.put("id", temp.id);
roadItem.put("name", temp.name);
road.add(0, roadItem);
temp = temp.parent;
}
roadItem = new HashMap<String, Object>();
roadItem.put("id", sn.id);
roadItem.put("name", sn.name);
road.add(0, roadItem);
}
result.put("road", road);
result.put("len", road.size());
return result;
}
/**
* 寻路AI 此方法无法用于多线程并发
* @param cNode
* @param end
* @param fNode
*/
private static boolean findRoadAI(List<Node> cNode, Node end, List<Node> fNode)
{
//TODO: 此方法无法用于多线程并发
if(cNode.size() == 0) return false;
List<Node> newCNode = new ArrayList<Node>(); // 当前到达节点
for(Node item:cNode)
{
for(Node ci:item.children)
{
if(ci == end)
{
ci.parent = item;
return true;
}
if(fNode.contains(ci))
continue;
ci.parent = item;
newCNode.add(ci);
fNode.add(ci);
}
}
return findRoadAI(newCNode, end, fNode);
}
/**
* 构建路线数
*/
private static void buildTree()
{
allNode = new HashMap<Integer, Node>();
PointsDaoImpl pdi = new PointsDaoImpl();
Node item;
for(Map<String, Object> pi:pdi.getPoints())
{
item = new Node();
item.id = (int) pi.get("id");
item.name = (String) pi.get("pname");
item.type = (int) pi.get("type");
allNode.put(item.id, item);
}
RoadDaoIpml rdi = new RoadDaoIpml();
Node start = null;
Map<String, Object> currentRoad = null;
Node preItem = null;
Node currentItem;
for(Map<String, Object> pi:rdi.getRoadPoints())
{
currentItem = allNode.get(pi.get("pointId"));
if(currentRoad == null || !pi.get("roadId").equals(currentRoad.get("roadId"))) // 切换路线
{
if(currentRoad != null && start != null && currentRoad.get("type").equals(2))
{
preItem.children.add(start);
start.children.add(preItem);
// start.parent = preItem;
// preItem.parent = start;
}
currentRoad = pi;
start = currentItem;
}
else
{
preItem.children.add(currentItem);
currentItem.children.add(preItem);
// currentItem.parent = preItem;
// preItem.parent = currentItem;
}
preItem = currentItem;
}
// 如果最后一个站点是环形线路终点
if(currentRoad != null && preItem != null && start != null && currentRoad.get("type").equals(2))
{
preItem.children.add(start);
start.children.add(preItem);
// start.parent = preItem;
// preItem.parent = start;
}
start = null;
currentRoad = null;
preItem = null;
currentItem = null;
}
}

复制代码

Node.java

package com.swift.util.tree;
import java.util.ArrayList;
import java.util.List;
public class Node{
public Node parent;
public List<Node> children = new ArrayList<>();
public String name;
public int type;
public int id;
}

复制代码

RoadDaoIpml.java

package com.swift.dao;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import com.swift.connect.DataBaseManager;
public class RoadDaoIpml {
public String addRoad()
{
return null;
}
public List<Map<String, Object>> getRoads()
{
List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>();
String sql = "select * from road order by Id";
DataBaseManager db = null;
try {
db = DataBaseManager.getDefaultConnection();
db.createStmt();
ResultSet result = db.getResult(sql);
Map<String, Object> item;
while(result.next())
{
item = new HashMap<String, Object>();
item.put("id", result.getInt("Id"));
item.put("rname", result.getString("rname"));
item.put("type", result.getInt("rtype"));
item.put("numpoint", result.getInt("numpoint"));
resultList.add(item);
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
finally{
if(db != null)
try {
db.close();
} catch (SQLException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return resultList;
}
public List<Map<String, Object>> getRoadPoints()
{
List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>();
String sql = "select t1.pindex, t1.pointId,t1.roadId, t2.rname,t2.rtype, t2.numpoint " +
"from roadpoint t1, road t2 " +
"where t2.Id = t1.roadId " +
"order by t2.Id, t1.pindex";
DataBaseManager db = null;
try {
db = DataBaseManager.getDefaultConnection();
db.createStmt();
ResultSet result = db.getResult(sql);
Map<String, Object> item;
while(result.next())
{
item = new HashMap<String, Object>();
item.put("pindex", result.getInt("pindex"));
item.put("rname", result.getString("rname"));
item.put("type", result.getInt("rtype"));
item.put("pointId", result.getInt("pointId"));
item.put("numpoint", result.getInt("numpoint"));
item.put("roadId", result.getInt("roadId"));
resultList.add(item);
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
finally{
if(db != null)
try {
db.close();
} catch (SQLException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return resultList;
}
}

复制代码

下面是获取数据的类不重要可以不看

PointsDaoImpl.java

package com.swift.dao;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.apache.log4j.Logger;
import com.swift.connect.DataBaseManager;
public class PointsDaoImpl {
private static Logger logger = Logger.getLogger(PointsDaoImpl.class);
public List<Map<String, Object>> getPoints()
{
List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>();
String sql = "select * from points order by ename";
DataBaseManager db = null;
try {
db = DataBaseManager.getDefaultConnection();
db.createStmt();
ResultSet result = db.getResult(sql);
Map<String, Object> item;
while(result.next())
{
item = new HashMap<String, Object>();
item.put("id", result.getInt("Id"));
item.put("pname", result.getString("pname"));
item.put("type", result.getInt("ptype"));
item.put("ename", result.getString("ename"));
resultList.add(item);
}
logger.info("########Points:");
logger.info(resultList.size());
} catch (Exception e) {
// TODO Auto-generated catch block
logger.error(e.toString());
e.printStackTrace();
}
finally{
if(db != null)
try {
db.close();
} catch (SQLException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return resultList;
}
}

复制代码

DataBaseManager.java

package com.swift.connect;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
import java.util.HashMap;
import org.apache.log4j.Logger;
import com.swift.util.ContextUtil;
public class DataBaseManager
{
private Connection con;
private ResultSet rs;
private Statement stmt;
private static Logger logger = Logger.getLogger(DataBaseManager.class);
/**
* @param url 例：jdbc:mysql://127.0.0.1/eshop
* @param user
* @param password
*/
private DataBaseManager(String url, String user, String password)
{
try{
Class.forName( "com.mysql.jdbc.Driver" );
// con=DriverManager.getConnection("jdbc:mysql://localhost:3306/eshop","root","123456");
con=DriverManager.getConnection(url + "?user=" + user + "&password=" + password + "&allowMultiQueries=true&useUnicode=true&characterEncoding=UTF8");
con.setAutoCommit(false);
}
catch ( ClassNotFoundException cnfex ) {
logger.error("Failed to load JDBC/ODBC driver." );
cnfex.printStackTrace();
System.exit( 1 );
}
catch(SQLException sqle)
{
sqle.printStackTrace();
logger.error(sqle.toString());
}
}
/**
* 查询数据库
* @param strSQL
* @return
*/
public ResultSet getResult(String strSQL)
{
try{
rs=stmt.executeQuery(strSQL);
return rs;
}
catch(SQLException sqle)
{
logger.error(sqle.toString());
return null;
}
}
public Statement createStmt() throws SQLException
{
stmt=con.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
return stmt;
}
/**
* 更新数据库
* @param strSQL
* @return
*/
public boolean updateSql(String strSQL)
{
try{
stmt.executeUpdate(strSQL);
con.commit();
return true;
}
catch(SQLException sqle)
{
try {
con.rollback();
} catch (SQLException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
logger.error(sqle.toString());
return false;
}
finally
{
}
}
/**
* 回收对象
* @throws SQLException
*/
public void close() throws SQLException
{
if(rs != null)
rs.close();
if(stmt != null)
stmt.close();
closeConnection();
rs = null;
stmt = null;
con = null;
// stack.push(this);
}
/**
* 关闭当前连接
*/
public void closeConnection()
{
try
{
if(con != null)
con.close();
}
catch(SQLException sqle)
{
logger.error(sqle.toString());
}
}
/** 连接池堆栈 */
// private static Stack<DataBaseManager> stack = new Stack<DataBaseManager>();
/**
* @param url 例：jdbc:mysql://127.0.0.1/eshop
* @param user
* @param password
* @return
*/
public static DataBaseManager getConnection(String url, String user, String password)
{
logger.info("###DBinfo:");
logger.info(url);
logger.info(user);
logger.info(password);
return new DataBaseManager(url, user, password);
}
public static DataBaseManager getDefaultConnection() throws Exception
{
HashMap<String, String> map = ContextUtil.getInstance().getDbCon();
return getConnection(map.get("url"), map.get("user"), map.get("password"));
}
}

复制代码

ContextUtil.java

package com.swift.util;
import java.io.File;
import java.net.URL;
import java.util.HashMap;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import org.w3c.dom.Document;
import org.w3c.dom.NamedNodeMap;
/**
* @author 破晓
*
*/
public class ContextUtil {
/**单例*/
private static ContextUtil instance;
private HashMap<String, String> dbCon = null;
private HashMap<String, String> serverCon = null;
/**
* 获取唯一实例
* @return
* @throws Exception
*/
public static ContextUtil getInstance() throws Exception
{
if(instance == null)
instance = new ContextUtil();
return instance;
}
private ContextUtil() throws Exception
{
initData();
}
private void initData() throws Exception
{
URL fileUrl = getClass().getResource("/config.xml");
if(fileUrl != null)
{
String fileName = fileUrl.toURI().getPath();
File f = new File(fileName);
DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
DocumentBuilder builder = factory.newDocumentBuilder();
Document doc = builder.parse(f);
dbCon = new HashMap<String, String>();
serverCon = new HashMap<String, String>();
NamedNodeMap db = doc.getElementsByTagName("db").item(0).getAttributes();
NamedNodeMap server = doc.getElementsByTagName("server").item(0).getAttributes();
dbCon.put("url", db.getNamedItem("url").getNodeValue());
dbCon.put("user", db.getNamedItem("user").getNodeValue());
dbCon.put("password", db.getNamedItem("password").getNodeValue());
serverCon.put("url", server.getNamedItem("url").getNodeValue());
}
}
public HashMap<String, String> getDbCon() {
return dbCon;
}
public HashMap<String, String> getServerCon() {
return serverCon;
}
}

复制代码

我是一个兵 · 发表于 2016-8-17 16:43:46

不错。。。。。。。

帐号		自动登录	找回密码
密码			立即注册

[数学算法] 广度优先遍历公交路线寻路算法JAVA实现

本帖子中包含更多资源

相关帖子

开源英雄

守望者

站长推荐 /4