目录
一、简述
二、前置配置
三、迪杰斯特拉算法
四、改进的迪杰斯特拉算法
五、贝尔曼福特算法
一、简述
图是一种比较常用的数据结构，将问题转换成图相关的思路也是比较常用的。
图的单源最短路径问题，也就是图中某一个节点到图中其他节点的最短路径大小，常用的算法就是迪杰斯特拉算法和贝尔曼福特算法，两者是从不同的角度来对这个问题进行分析的，但是迪杰斯特拉算法并不适用于有负权重的情况，而贝尔曼福特算法则是应用范围更广泛，能解决带有负权重问题的场景。
二、前置配置
边类：
package graph;
/**
* 边类
*/
public class Edge {
Vertex vertex;
int weight;
public Edge() {
}
public Edge(Vertex vertex) {
this.vertex = vertex;
}
public Edge(Vertex vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
public Vertex getVertex() {
return vertex;
}
public void setVertex(Vertex vertex) {
this.vertex = vertex;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
结点类：
package graph;
import java.util.List;
/**
* 顶点类
*/
public class Vertex {
String name;
List<Edge> edges;
boolean flag;//是否被访问过
int inDegree;//结点的入度
int status;//状态, 0-未访问过， 1-正在访问，用于检测环，2-已经访问过
int dist=Integer.MAX_VALUE;//距离
Vertex pre=null;
public Vertex() {
}
public Vertex(String name, List<Edge> edges) {
this.name = name;
this.edges = edges;
}
public Vertex(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Edge> getEdges() {
return edges;
}
public void setEdges(List<Edge> edges) {
this.edges = edges;
}
}
三、迪杰斯特拉算法
迪杰斯特拉算法是从节点出发来完成单源最短路径问题的，我们可以将整个图分为两个区域，一个区域就是已经找到从源点到该点的最短路径，另一个区域则是未找到的。
从已经找到的区域到未找到的区域的所有相连节点的边，从中取最小值，并将该边所对应的未找到区域的结点加入到已经找到找到的区域，并更改其最短路径。
最后，通过将所有联通的结点的最短路径找到，即可结束。
代码：
package graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Dijkstra {
public static void main(String[] args) {
Vertex v1=new Vertex("v1",new LinkedList<>());
Vertex v2=new Vertex("v2",new LinkedList<>());
Vertex v3=new Vertex("v3",new LinkedList<>());
Vertex v4=new Vertex("v4",new LinkedList<>());
Vertex v5=new Vertex("v5",new LinkedList<>());
Vertex v6=new Vertex("v6",new LinkedList<>());
v1.edges.add(new Edge(v3,9));
v1.edges.add(new Edge(v2,7));
v1.edges.add(new Edge(v6,14));
v2.edges.add(new Edge(v4,15));
v3.edges.add(new Edge(v4,11));
v3.edges.add(new Edge(v6,2));
v4.edges.add(new Edge(v5,6));
v6.edges.add(new Edge(v5,9));
List<Vertex> graph=new ArrayList<>();
graph.add(v1);
graph.add(v2);
graph.add(v3);
graph.add(v4);
graph.add(v5);
graph.add(v6);
dijkstra(graph,v1);
}
private static void dijkstra(List<Vertex> graph,Vertex vertex) {
ArrayList<Vertex> list=new ArrayList<>(graph);
vertex.dist=0;
while(!list.isEmpty()){
//选取当前顶点(距离最小的顶点)
Vertex curr=chooseMinDistVertex(list);
//更新当前顶点邻居距离
updateNeighboursDist(curr,list);
//移除当前节点
list.remove(curr);
}
for (Vertex vertex1 : graph) {
System.out.println(vertex1.name+" "+vertex1.dist +" "+(vertex1.pre==null?"null":vertex1.pre.name));
}
}
private static void updateNeighboursDist(Vertex curr, ArrayList<Vertex> list) {
for (Edge edge : curr.edges) {
Vertex n=edge.vertex;
if(list.contains(n)){
int dist= curr.dist+edge.weight;
if(dist<n.dist){
n.dist=dist;
n.pre=curr;
}
}
}
}
private static Vertex chooseMinDistVertex(ArrayList<Vertex> list) {
Vertex min=list.get(0);
for(int i=0;i<list.size();i++){
if(list.get(i).dist<min.dist){
min=list.get(i);
}
}
return min;
}
}
四、改进的迪杰斯特拉算法
我们发现每次寻找最小值的时候都需要遍历整个集合，时间复杂度为O(n)，因此，我们可以用优先队列来解决，优先队列会自动将优先级别高的排在前面，所以，我们只需要将其设置为边的权重越小优先级越高即可，每次只需要取出队首元素即可，时间复杂度为O(1)。
代码：
package graph;
import java.util.*;
/**
* 第二种算法的实现：采用优先级队列，减少选取最小距离时的时间复杂度，使用优先级队列直接获取头部元素
* 时间复杂度得到了改善
*/
public class DijkstraTwo {
public static void main(String[] args) {
Vertex v1=new Vertex("v1",new LinkedList<>());
Vertex v2=new Vertex("v2",new LinkedList<>());
Vertex v3=new Vertex("v3",new LinkedList<>());
Vertex v4=new Vertex("v4",new LinkedList<>());
Vertex v5=new Vertex("v5",new LinkedList<>());
Vertex v6=new Vertex("v6",new LinkedList<>());
v1.edges.add(new Edge(v3,9));
v1.edges.add(new Edge(v2,7));
v1.edges.add(new Edge(v6,14));
v2.edges.add(new Edge(v4,15));
v3.edges.add(new Edge(v4,11));
v3.edges.add(new Edge(v6,2));
v4.edges.add(new Edge(v5,6));
v6.edges.add(new Edge(v5,9));
List<Vertex> graph=new ArrayList<>();
graph.add(v1);
graph.add(v2);
graph.add(v3);
graph.add(v4);
graph.add(v5);
graph.add(v6);
dijkstra(graph,v1);
}
private static void dijkstra(List<Vertex> graph,Vertex vertex) {
PriorityQueue<Vertex> queue=new PriorityQueue<>(Comparator.comparing(v->v.dist));//优先级队列,按照距离来升序排列
for (Vertex vertex1 : graph) {
queue.offer(vertex1);
}
vertex.dist=0;
while(!queue.isEmpty()){
//选取当前顶点(距离最小的顶点)
Vertex curr=queue.peek();
//更新当前顶点邻居距离
updateNeighboursDist(curr,queue);
//移除当前节点
queue.poll();
curr.flag=true;
}
for (Vertex vertex1 : graph) {
System.out.println(vertex1.name+" "+vertex1.dist +" "+(vertex1.pre==null?"null":vertex1.pre.name));
}
}
private static void updateNeighboursDist(Vertex curr, PriorityQueue<Vertex> queue) {
for (Edge edge : curr.edges) {
Vertex n=edge.vertex;
if(queue.contains(n)){
int dist= curr.dist+edge.weight;
if(dist<n.dist){
n.dist=dist;
n.pre=curr;
queue.offer(n);
}
}
}
}
}
五、贝尔曼福特算法
贝尔曼福特算法是以边为元素来考虑的，每次从所有边中，找出最小的，并尝试更改边两边结点的最短距离，如果小于原先值就修改，否则就不变。
算法需要执行（边数-1）次，每次对所有的边上的进行尝试更改。
代码：
package graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* 迪杰斯特拉算法不适合存在负值边的情况，
* 而贝尔曼福特算法能够解决这种问题，是以边为元素来处理的
*/
public class BellmanFord {
public static void main(String[] args) {
Vertex v1=new Vertex("v1",new LinkedList<>());
Vertex v2=new Vertex("v2",new LinkedList<>());
Vertex v3=new Vertex("v3",new LinkedList<>());
Vertex v4=new Vertex("v4",new LinkedList<>());
Vertex v5=new Vertex("v5",new LinkedList<>());
Vertex v6=new Vertex("v6",new LinkedList<>());
v1.edges.add(new Edge(v3,9));
v1.edges.add(new Edge(v2,7));
v1.edges.add(new Edge(v6,14));
v2.edges.add(new Edge(v4,15));
v3.edges.add(new Edge(v4,11));
v3.edges.add(new Edge(v6,2));
v4.edges.add(new Edge(v5,6));
v6.edges.add(new Edge(v5,9));
List<Vertex> graph=new ArrayList<>();
graph.add(v1);
graph.add(v2);
graph.add(v3);
graph.add(v4);
graph.add(v5);
graph.add(v6);
bellmanFord(graph,v1);
}
private static void bellmanFord(List<Vertex> graph, Vertex v1) {
v1.dist=0;
int size=graph.size();
for(int i=0;i<size-1;i++){//循环边数-1次，找出除了根节点外的其他节点
//遍历所有的边
for (Vertex s : graph) {
for (Edge edge : s.edges) {
//处理每一条边
Vertex e = edge.vertex;
if(s.dist!=Integer.MAX_VALUE && s.dist+edge.weight<e.dist){
e.dist=s.dist+edge.weight;
}
}
}
}
for (Vertex vertex : graph) {
System.out.println(vertex.name+" "+vertex.dist);
}
}
}
