這篇文章主要介紹了java實現最短路徑演算法之Dijkstra演算法， Dijkstra演算法是最短路徑演算法中為人熟知的一種，是單起點全路徑演算法，有興趣的可以了解
#前言
Dijkstra演算法是最短路徑演算法中為人熟知的一種，是單起點全路徑演算法。該演算法被稱為是「貪心演算法」的成功典範。本文接下來將嘗試以最通俗的語言來介紹這個偉大的演算法，並賦予java實作程式碼。
一、知識準備：
1、表示圖的資料結構
用於儲存圖的資料結構有多種，本演算法中筆者使用的是鄰接矩陣。
圖的鄰接矩陣儲存方式是用兩個陣列來表示圖。一個一維數組儲存圖中頂點信息，一個二維數組（鄰接矩陣）儲存圖中的邊或弧的信息。
設圖G有n個頂點，則鄰接矩陣為n*n的方陣，定義為：
2、單一起點全路徑
所謂單一起點全路徑，就是指在一個圖中，從一個起點出發，到所有節點的最短路徑。3、圖論的基本知識(讀者需自行尋找相關資料)
4、互補鬆弛條件
設標量d1,d2,....,dN滿足dj13e369f29ccc06a1a70d3aa3e35c7a1c di + aij（違反鬆弛條件）,則令dj = di + aij , （如果j已經從V中移除過，說明其最小距離已經計算出，不參與此次計算）可以看到在演算法的運算工程中，節點的d值是單調不增的具體演算法圖解如下
# 
#
三、java程式碼實作
public class Vertex implements Comparable<Vertex>{
/**
* 节点名称(A,B,C,D)
*/
private String name;
/**
* 最短路径长度
*/
private int path;
/**
* 节点是否已经出列(是否已经处理完毕)
*/
private boolean isMarked;
public Vertex(String name){
this.name = name;
this.path = Integer.MAX_VALUE; //初始设置为无穷大
this.setMarked(false);
}
public Vertex(String name, int path){
this.name = name;
this.path = path;
this.setMarked(false);
}
@Override
public int compareTo(Vertex o) {
return o.path > path?-1:1;
}
}#########public class Graph {
/*
* 顶点
*/
private List<Vertex> vertexs;
/*
* 边
*/
private int[][] edges;
/*
* 没有访问的顶点
*/
private Queue<Vertex> unVisited;
public Graph(List<Vertex> vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
initUnVisited();
}
/*
* 搜索各顶点最短路径
*/
public void search(){
while(!unVisited.isEmpty()){
Vertex vertex = unVisited.element();
//顶点已经计算出最短路径，设置为"已访问"
vertex.setMarked(true);
//获取所有"未访问"的邻居
List<Vertex> neighbors = getNeighbors(vertex);
//更新邻居的最短路径
updatesDistance(vertex, neighbors);
pop();
}
System.out.println("search over");
}
/*
* 更新所有邻居的最短路径
*/
private void updatesDistance(Vertex vertex, List<Vertex> neighbors){
for(Vertex neighbor: neighbors){
updateDistance(vertex, neighbor);
}
}
/*
* 更新邻居的最短路径
*/
private void updateDistance(Vertex vertex, Vertex neighbor){
int distance = getDistance(vertex, neighbor) + vertex.getPath();
if(distance < neighbor.getPath()){
neighbor.setPath(distance);
}
}
/*
* 初始化未访问顶点集合
*/
private void initUnVisited() {
unVisited = new PriorityQueue<Vertex>();
for (Vertex v : vertexs) {
unVisited.add(v);
}
}
/*
* 从未访问顶点集合中删除已找到最短路径的节点
*/
private void pop() {
unVisited.poll();
}
/*
* 获取顶点到目标顶点的距离
*/
private int getDistance(Vertex source, Vertex destination) {
int sourceIndex = vertexs.indexOf(source);
int destIndex = vertexs.indexOf(destination);
return edges[sourceIndex][destIndex];
}
/*
* 获取顶点所有(未访问的)邻居
*/
private List<Vertex> getNeighbors(Vertex v) {
List<Vertex> neighbors = new ArrayList<Vertex>();
int position = vertexs.indexOf(v);
Vertex neighbor = null;
int distance;
for (int i = 0; i < vertexs.size(); i++) {
if (i == position) {
//顶点本身，跳过
continue;
}
distance = edges[position][i]; //到所有顶点的距离
if (distance < Integer.MAX_VALUE) {
//是邻居(有路径可达)
neighbor = getVertex(i);
if (!neighbor.isMarked()) {
//如果邻居没有访问过，则加入list;
neighbors.add(neighbor);
}
}
}
return neighbors;
}
/*
* 根据顶点位置获取顶点
*/
private Vertex getVertex(int index) {
return vertexs.get(index);
}
/*
* 打印图
*/
public void printGraph() {
int verNums = vertexs.size();
for (int row = 0; row < verNums; row++) {
for (int col = 0; col < verNums; col++) {
if(Integer.MAX_VALUE == edges[row][col]){
System.out.print("X");
System.out.print(" ");
continue;
}
System.out.print(edges[row][col]);
System.out.print(" ");
}
System.out.println();
}
}
}#########public class Test {
public static void main(String[] args){
List<Vertex> vertexs = new ArrayList<Vertex>();
Vertex a = new Vertex("A", 0);
Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex d = new Vertex("D");
Vertex e = new Vertex("E");
Vertex f = new Vertex("F");
vertexs.add(a);
vertexs.add(b);
vertexs.add(c);
vertexs.add(d);
vertexs.add(e);
vertexs.add(f);
int[][] edges = {
{Integer.MAX_VALUE,6,3,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
{6,Integer.MAX_VALUE,2,5,Integer.MAX_VALUE,Integer.MAX_VALUE},
{3,2,Integer.MAX_VALUE,3,4,Integer.MAX_VALUE},
{Integer.MAX_VALUE,5,3,Integer.MAX_VALUE,5,3},
{Integer.MAX_VALUE,Integer.MAX_VALUE,4,5,Integer.MAX_VALUE,5},
{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,5,Integer.MAX_VALUE}
};
Graph graph = new Graph(vertexs, edges);
graph.printGraph();
graph.search();
}
}以上是Java中關於最短路徑演算法之Dijkstra演算法的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！