1.图的两种表示方式:
a. 邻接矩阵 二维数组搞定
b. 邻接表：Map<Vertext,List<Edge>>搞定
其中临街矩阵适用于稠密图，即图上的任意两点之间均（差不多都）存在一条边。
而A到B之间的路线，显然是稀疏图，果断的选用邻接表。
2.加权有向图最短路径问题，典型的dijkstra最短路径算法。
import java.util.*;
public class Dijkstra {
//定义顶点Vertex类
static class Vertex{
private final static int infinite_dis = Integer.MAX_VALUE;
private Stirng name; //节点名字
private boolean known; //此节点是否已知
private int adjuDist; //此节点距离
private Vertex parent; //当前从初始化节点到此节点的最短路径下的父亲节点
public Vertex(){
this.known = false;
this.adjuDist = infinite_dis;
this.parent = null;
}
public Vertex(String name){
this();
this.name = name;
}
public String getName(){
return name;
}
public void setName(String name) {
this.name = name;
}
public boolean isKnown(){
return known;
}
public void setKnown(boolean known){
this.known = known;
}
public int getAdjuDist(){
return adjuDist;
}
public void setAdjuDist(int adjuDist){
this.adjuDist = adjuDist;
}
public Vertex getParent(){
return parent;
}
public void setParent(Vertex parent){
this.parent = parent;
}
public boolean equals(Object obj){
if(!(obj instanceof Vertex)){
throw new ClassCastException("an object to compare with a Vertex");
}
if(this.name==null){
throw new NullPointerException("name of Vertex to be compared cannot be null!");
return this.name.equals(((Vertex)obj).getName());
}
}
}
//定义有向边类
static class Edge{
//此有向边的起始点
private Vertex startVertex;
//此有向边的终点
private Vertex endVertex;
//此有向边的权值
private int weight;
public Edge(Vertex startVertex,Vertex endVertex,int weight){
this.startVertex = startVertex;
this.endVertex = endVertex;
this.weight = weight;
}
public Vertex getStartVertex(){
return startVertex;
}
public Vertex getEndVertex(){
return endVertex;
}
public int getWeight(){
return weight;
}
public void setStartVertex(Vertex startVertex){
this.startVertex = startVertex;
}
public void setEndVertex(Vertex endVertex){
this.endVertex = endVertex;
}
public void setWeight(int weight){
this.weight = weight;
}
}
private List<Vertex> vertexList; //图的顶点集
private Map<Vertex,List<Edge> > ver_edgeList_map; //图的每个顶点对应的有向边
public Dijkstra(List<Vertex> vertexList, Map<Vertex, List<Edge>> ver_edgeList_map) {
this.vertexList = vertexList;
this.ver_edgeList_map = ver_edgeList_map;
}
public void setRoot(Vertex v){
v.setParent(null);
v.setAdjuDist(0);
}
//从初始节点开始递归更新邻接表
private void updateChildren(Vertex v){
if (v==null){
return;
}
if (ver_edgeList_map.get(v)==null || ver_edgeList_map.get(v).size()==0){
return;
}
List<Vertex> childrenList = new LinkedList<Vertex>();
for (Edge e:ver_edgeList_map.get(v)){
Vertex childVertex = e.getEndVertex();
//如果子节点之前未知,则把当前子节点加入更新列表
if (!childVertex.isKnown()){
childVertex.setKnown(true);
childVertex.setAdjuDist(v.getAdjuDist()+e.getWeight());
childVertex.setParent(v);
childrenList.add(childVertex);
}
//子节点之前已知,则比较子节点的adjudist&&nowDist
int nowDist = v.getAdjuDist() + e.getWeight();
if (nowDist >= childVertex.getAdjuDist()){
continue;
}else {
childVertex.setAdjuDist(nowDist);
childVertex.setParent(v);
}
}
//更新每一个子节点
for (Vertex vc:childrenList){
updateChildren(vc);
}
}
/**
*
* @param startIndex dijkstra遍历的起点节点下标
* @param destIndex dijkstra遍历的终点节点下标
*/
public void dijkstraTravasal(int startIndex,int destIndex){
Vertex start = vertexList.get(startIndex);
Vertex dest = vertexList.get(destIndex);
String path = "[" + dest.getName() + "]";
setRoot(start);
updateChildren(vertexList.get(startIndex));
int shortest_length = dest.getAdjuDist();
while ((dest.getParent()!=null)&&(!dest.equals(start))){
path = "[" + dest.getParent().getName() +"] --> "+path;
dest = dest.getParent();
}
System.out.println("["+vertexList.get(startIndex).getName()+"] to ["+
vertexList.get(destIndex).getName()+"] dijkstra shortest path:: "+path);
System.out.println("shortest length::" + shortest_length);
}
public static void main(String[] args) {
Vertex v1= new Vertex("v1");
Vertex v2= new Vertex("v2");
Vertex v3= new Vertex("v3");
Vertex v4= new Vertex("v4");
Vertex v5= new Vertex("v5");
Vertex v6= new Vertex("v6");
Vertex v7= new Vertex("v7");
List<Vertex> verList = new LinkedList<Dijkstra.Vertex>();
verList.add(v1);
verList.add(v2);
verList.add(v3);
verList.add(v4);
verList.add(v5);
verList.add(v6);
verList.add(v7);
Map<Vertex, List<Edge>> vertex_edgeList_map = new HashMap<Vertex, List<Edge>>();
List<Edge> v1List = new LinkedList<Dijkstra.Edge>();
v1List.add(new Edge(v1,v2,2));
v1List.add(new Edge(v1,v4,1));
List<Edge> v2List = new LinkedList<Dijkstra.Edge>();
v2List.add(new Edge(v2,v4,3));
v2List.add(new Edge(v2,v5,10));
List<Edge> v3List = new LinkedList<Dijkstra.Edge>();
v3List.add(new Edge(v3,v1,4));
v3List.add(new Edge(v3,v6,5));
List<Edge> v4List = new LinkedList<Dijkstra.Edge>();
v4List.add(new Edge(v4,v3,2));
v4List.add(new Edge(v4,v5,2));
v4List.add(new Edge(v4,v6,8));
v4List.add(new Edge(v4,v7,4));
List<Edge> v5List = new LinkedList<Dijkstra.Edge>();
v5List.add(new Edge(v5,v7,6));
List<Edge> v6List = new LinkedList<Dijkstra.Edge>();
List<Edge> v7List = new LinkedList<Dijkstra.Edge>();
v7List.add(new Edge(v7,v6,1));
vertex_edgeList_map.put(v1, v1List);
vertex_edgeList_map.put(v2, v2List);
vertex_edgeList_map.put(v3, v3List);
vertex_edgeList_map.put(v4, v4List);
vertex_edgeList_map.put(v5, v5List);
vertex_edgeList_map.put(v6, v6List);
vertex_edgeList_map.put(v7, v7List);
Dijkstra g = new Dijkstra(verList, vertex_edgeList_map);
// g.dijkstraTravasal(1, 5);
g.dijkstraTravasal(0, 6);
}
}
测试用图
dijkstra.png
输出结果: [v1] to [v7] dijkstra shortest path:: [v1] --> [v4] --> [v7]
shortest length::5
网友评论