最短路径算法（旅游规划实例java语言）

Dijkstra算法

简介

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点（不是所有节点到所有节点）的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止

算法思想

通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。（u中间的距离如何计算，是通过s集合中的顶点作为中转点计算得出，s最开始只有一个起始点，但不断地从u中取出min距离的顶点到s，再根据这个顶点作为中转点更新u中的距离）

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

————————————————

参考链接：https://blog.csdn.net/xushiyu1996818/article/details/90516598

/**用dijkstra算法求出first节点到其他节点的最短距离 

* 声明两个set，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点 

* 声明两个map，一个map为distance，key为vertex，value为double，是计算现在得到的这个vertex距离起始点的最短路径 

* 一个map为path，key为vertex，value为vertex，是出发点到结束点的最短距离的路径的最后的中转节点 

* 初始阶段，将所有节点放入open 

* distance里面先初始为doubleMax，Path先初始为vertex自己 

* 将起始点放入close，设置distance=0，path=自己，更新起始点周围的节点的距离，设置他们的distance=边的距离，path=起始点 

* 以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点（遍历open中的vertex,找到distance最小的vertex） 

* 放入close并从新计算路径，直至close包含所有子节点（或者说open为空） 

* @param first

* @return 返回一个map为distance，key为vertex，value为double，是计算现在得到的这个vertex距离起始点的最短路径 

*/

public HashMap<Vertex<T>, Double> getSmallestDistanceDijkstra(String first){

Set<Vertex<T>> open=new HashSet<>();

Set<Vertex<T>> close=new HashSet<>();

HashMap<Vertex<T>, Vertex<T>> path=new HashMap<>();

HashMap<Vertex<T>, Double> distance=new HashMap<>();

Set<Vertex<T>> set=getVertexSet();

Vertex<T> firstVertex=vertexMap.get(first);

Edge edge;

if(firstVertex==null){

return distance;

}

//初始阶段，将所有节点放入open,distance里面先初始为doubleMax，Path先初始为vertex自己

for(Vertex<T> vertex:set){

open.add(vertex);

distance.put(vertex, Double.MAX_VALUE);

path.put(vertex, vertex);

}

//将起始点放入close，设置distance=0，path=自己，更新起始点周围的节点的距离，设置他们的distance=边的距离，path=起始点

open.remove(firstVertex);

close.add(firstVertex);

distance.put(firstVertex, 0.0);

path.put(firstVertex, firstVertex);

Iterator<Edge> edgeIterator=firstVertex.getEdgeIterator();

while(edgeIterator.hasNext()){

edge=edgeIterator.next();

Vertex<T> endVertex=edge.getEndVertex();

distance.put(endVertex, edge.getWeight());

path.put(endVertex, firstVertex);

}

//以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点（遍历open中的vertex,找到distance最小的vertex）

//放入close并从新计算路径，直至close包含所有子节点（或者说open为空）

while(!open.isEmpty()){

Double minDistance=Double.MAX_VALUE;

Vertex<T> minVertex=null;

for(Vertex<T> vertex:open){

if(minDistance>distance.get(vertex)){

//遍历open中的vertex,找到distance最小的vertex

minDistance=distance.get(vertex);

minVertex=vertex;

}

}

////放入close并从新计算路径，直至close包含所有子节点（或者说open为空）

open.remove(minVertex);

close.add(minVertex);

//System.out.println("加入节点："+minVertex.getLabel());

edgeIterator=minVertex.getEdgeIterator();

while(edgeIterator.hasNext()){

edge=edgeIterator.next();

Vertex<T> endVertex=edge.getEndVertex();

Double weight=edge.getWeight();

//如果之前的距离>初始到minVertex+minVertex到endVertex，就替换

if(distance.get(endVertex)>distance.get(minVertex)+weight){

distance.put(endVertex, distance.get(minVertex)+weight);

path.put(endVertex, minVertex);

}

}

}

for(Vertex<T> vertex:set){

System.out.println("到顶点："+vertex.getLabel()+

" ，最短距离为："+distance.get(vertex)+" ，最后中转点为:"+path.get(vertex).getLabel());

}

return distance;

}

下面以欧洲旅游规划为例模拟欧洲铁路系统中两个城市之间最便宜的路线

public class Service {//服务类

String name; int cost; int distance; Service next;

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getCost() {

return cost;

}

public void setCost(int cost) {

this.cost = cost;

}

public int getDistance() {

return distance;

}

public void setDistance(int distance) {

this.distance = distance;

}

public Service(String name, int cost, int distance) {

super();

this.name = name; this.cost = cost； this.distance = distance;

next=null;

}

}

public class City {//代表图上的结点

Service first; String name;

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public City(String name) {

super();

this.name = name;

first=null;

}

public void addService(Service s) {

if(first==null) {

first=s;

}else {

Service w=first;

while(w.next!=null) {

w=w.next;

}w.next=s;}

}

public int getdistance(String name) {

Service w=first;

while(w!=null) {

if(w.getName().equals(name)) {

return w.distance;

}

w=w.next;

}

return 0;

} }

public class RailSystem {//模拟铁路系统

SeqList<City> citylist;

HashMap<City, City>path; HashMap<City,Integer>distance;

String from_city;

City currentcity;

public RailSystem() {

citylist= new SeqList<City>(20);

}

public void addCity(String name) {

citylist.add(new City(name));

}

public City getCity(String name) {

for(int i=0;i<citylist.size();i++) {

if(citylist.get(i).getName().equals(name)) {

return citylist.get(i);

}

}return null;

}

public void calc_route(String first){//计算各结点最小价格

from_city=null;

Set<City> cityin=new HashSet<>();//未遍历的结点

Set<City> cityout=new HashSet<>();//已遍历的结点

path=new HashMap<>();//各结点的先驱结点

distance=new HashMap<>();//起始点到此结点的距离

Service edge;

for(int i=0;i<citylist.size();i++) {//把所有结点放入cityin

cityin.add(citylist.get(i));

distance.put(citylist.get(i), Integer.MAX_VALUE);

path.put(citylist.get(i),citylist.get(i));

}

City firstCity=getCity(first);//设置初始状态

currentcity=firstCity;

cityin.remove(firstCity);

cityout.add(firstCity);

distance.put(firstCity, 0);

path.put(firstCity, firstCity);

edge=firstCity.first;

while(edge !=null) {

City nextcity=getCity(edge.name);

distance.put(nextcity, edge.getCost());

path.put(nextcity, firstCity);

edge=edge.next;

}

while(!cityin.isEmpty()) {//下面开始由中心向外一层层遍历

int minDistance=Integer.MAX_VALUE;

City minCity=null;

for(City c:cityin) {//得到距离(价格)最近的城市

if(minDistance >distance.get(c)){

minDistance=distance.get(c);

minCity=c;

}

}

cityin.remove(minCity);

cityout.add(minCity);

/////////////////////下面要更新距离

if(minCity!=null) {

edge=minCity.first;}

while(edge !=null) {

City nextcity=getCity(edge.name);

int cost=edge.cost;

if(distance.get(nextcity)>distance.get(minCity)+cost) {

distance.put(nextcity, distance.get(minCity)+cost);

path.put(nextcity, minCity);

}

edge=edge.next;

}

}

}

public String recover_route(String name) {//根据目的地返回路线与价格

SeqList<City> route_=new SeqList<City>(20);

String _route="The cheapest route from "+currentcity.name+" to "+name+"\n";

int length=0;

City endCity=getCity(name);

int cost=distance.get(endCity);

City city=endCity;

while(endCity !=currentcity) {

endCity=path.get(city);

length=length+city.getdistance(endCity.name);

route_.add(city);

city=endCity;

}route_.add(city);

_route=_route+"costs "+String.valueOf(cost)+" euros and spans "+String.valueOf(length)+" kilometers"+"\n";

for(int i=route_.size()-1;i>=0;i--) {

_route=_route+route_.get(i).name;

if(route_.get(i-1)!=null) {

_route=_route+" to ";

}

}

return from_city=_route;

}

public void reset() {//系统重置

path=new HashMap<>();

distance=new HashMap<>();

}

public void loadService(String filename) throws IOException {//装载结点数据

File file=new File(filename);

FileReader fr=new FileReader(file);

BufferedReader br=new BufferedReader(fr);

String data=null;

while((data=br.readLine())!=null) {

String[]datas=data.split(" ");

if(getCity(datas[0])==null) {

addCity(datas[0]);

getCity(datas[0]).addService(new Service(datas[1],Integer.parseInt(datas[2]),Integer.parseInt(datas[3])));

}else {

getCity(datas[0]).addService(new Service(datas[1],Integer.parseInt(datas[2]),Integer.parseInt(datas[3])));

}

}

}

public void run() throws IOException {//运行

loadService("F:\\java\\workspace\\Exprience4\\services.txt");

String start=" ";

String end=" ";

while(!start.equals("quit") &&!end.equals("quit")) {

System.out.println("Enter a start and destination city: <'quit' to exit>");

Scanner in=new Scanner(System.in);

start=in.next();

end=in.next();

if(!(getCity(start)==null)&& !(getCity(end)==null)) {

calc_route(start);

System.out.println(recover_route(end));}

}

}