参考实现： https://blog.csdn.net/qq_39630587/article/details/79030812
最短路径：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。
Drjkstra 与 prim区别：
-
Prim是计算最小生成树的算法，比如为N个村庄修路，怎么修花销最少。
Dijkstra是计算最短路径的算法，比如从a村庄走到其他任意村庄的距离。 -
Prim算法中有一个统计总len的变量，每次都要把到下一点的距离加到len中；
Dijkstra算法中却没有，只需要把到下一点的距离加到cls数组中即可； -
Prim算法的更新操作更新的cls是已访问集合到未访问集合中各点的距离；
for (j=0;j<n;j++)
{
if (!visited[j] && map[j][nid]<adjset[j])//更新条件：j点未访问，加入新点后已访问集合到j的距离变小了
{
adjset[j] = map[j][nid];
}
}
Dijkstra算法的更新操作更新的cls是源点到未访问集合中各点的距离，已经访问过的相当于已经找到源点到它的最短距离了；
for (j=1;j<=n;j++)
{
if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j])//更新条件：j点未访问，新点与j点之间有路，
cls[j]=cls[nxt]+map[nxt][j];
}
Dijkstra 狄克斯特拉
- 贪心算法
- 将节点维护为两个集合： S集合（已经求出最短路径的节点），V-S集合（尚未求出最短路径的节点）
- 维护三个计算队列：
- 源节点s0到各个节点的最短距离
- 每个节点是否被访问过
- 使得s0到各节点距离最近的跳板节点
public class GraphByMatrix {
public static final boolean UNDIRECTED_GRAPH = false;//无向图标志
public static final boolean DIRECTED_GRAPH = true;//有向图标志
public static final boolean ADJACENCY_MATRIX = true;//邻接矩阵实现
public static final boolean ADJACENCY_LIST = false;//邻接表实现
public static final int MAX_VALUE = Integer.MAX_VALUE;
private boolean graphType;
private boolean method;
private int vertexSize;
private int matrixMaxVertex;
//存储所有顶点信息的一维数组
private Object[] vertexesArray;
//存储图中顶点之间关联关系的二维数组,及边的关系
private int[][] edgesMatrix;
// 记录第i个节点是否被访问过
private boolean[] visited;
/**
* @param graphType 图的类型：有向图/无向图
* @param method 图的实现方式：邻接矩阵/邻接表
*/
public GraphByMatrix(boolean graphType, boolean method, int size) {
this.graphType = graphType;
this.method = method;
this.vertexSize = 0;
this.matrixMaxVertex = size;
if (this.method) {
visited = new boolean[matrixMaxVertex];
vertexesArray = new Object[matrixMaxVertex];
edgesMatrix = new int[matrixMaxVertex][matrixMaxVertex];
//对数组进行初始化，顶点间没有边关联的值为Integer类型的最大值
for (int row = 0; row < edgesMatrix.length; row++) {
for (int column = 0; column < edgesMatrix.length; column++) {
edgesMatrix[row][column] = MAX_VALUE;
}
}
}
}
/********************最短路径****************************/
//计算一个顶点到其它一个顶点的最短距离
public void Dijkstra(Object obj) throws Exception {
Dijkstra(getVertexIndex(obj));
}
public void Dijkstra(int v0) {
int[] dist = new int[matrixMaxVertex];
int[] prev = new int[matrixMaxVertex];
//初始化visited、dist和path
for (int i = 0; i < vertexSize; i++) {
//一开始假定取直达路径最短
dist[i] = edgesMatrix[v0][i];
visited[i] = false;
//直达情况下的最后经由点就是出发点
if (i != v0 && dist[i] < MAX_VALUE)
prev[i] = v0;
else
prev[i] = -1; //无直达路径
}
//初始时源点v0∈visited集，表示v0 到v0的最短路径已经找到
visited[v0] = true;
// 下来假设经由一个点中转到达其余各点,会近些,验证之
// 再假设经由两个点中转,会更近些,验证之,.....
// 直到穷举完所有可能的中转点
int minDist;
int v = 0;
for (int i = 1; i < vertexSize; i++) {
//挑一个距离最近经由点,下标装入 v
minDist = MAX_VALUE;
for (int j = 0; j < vertexSize; j++) {
if ((!visited[j]) && dist[j] < minDist) {
v = j; // 经由顶点j中转则距离更短
minDist = dist[j];
}
}
visited[v] = true;
/*顶点v并入S，由v0到达v顶点的最短路径为min.
假定由v0到v，再由v直达其余各点，更新当前最后一个经由点及距离*/
for (int j = 0; j < vertexSize; j++) {
if ((!visited[j]) && edgesMatrix[v][j] < MAX_VALUE) {
if (minDist + edgesMatrix[v][j] <= dist[j]) {
//如果多经由一个v点到达j点的 最短路径反而要短,就更新
dist[j] = minDist + edgesMatrix[v][j];
prev[j] = v; //经由点的序号
}
}
}
}
for (int i = 1; i < matrixMaxVertex; i++) {
System.out.println("**" + vertexesArray[v0] + "-->" +vertexesArray[i] + " 的最短路径是：" + dist[i]);
}
}
//获取顶点值在数组里对应的索引
private int getVertexIndex(Object obj) throws Exception {
int index = -1;
for (int i = 0; i < vertexSize; i++) {
if (vertexesArray[i].equals(obj)) {
index = i;
break;
}
}
if (index == -1) {
throw new Exception("没有这个值！");
}
return index;
}
/**
* 单源最短路径算法，用于计算一个节点到其他!!所有节点!!的最短路径
*/
public void Dijkstra2(int v0) {
// LinkedList实现了Queue接口 FIFO
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < vertexSize; i++) {
visited[i] = false;
}
//这个循环是为了确保每个顶点都被遍历到
for (int i = 0; i < vertexSize; i++) {
if (!visited[i]) {
queue.add(i);
visited[i] = true;
while (!queue.isEmpty()) {
int row = queue.remove();
System.out.print(vertexesArray[row] + "-->");
for (int k = getMin(row); k >= 0; k = getMin(row)) {
if (!visited[k]) {
queue.add(k);
visited[k] = true;
}
}
}
}
}
}
private int getMin( int row) {
int minDist = MAX_VALUE;
int index = 0;
for (int j = 0; j < vertexSize; j++) {
if ((!visited[j]) && edgesMatrix[row][j] < minDist) {
minDist = edgesMatrix[row][j];
index = j;
}
}
if (index == 0) {
return -1;
}
return index;
}
public boolean addVertex(Object val) {
assert (val != null);
vertexesArray[vertexSize] = val;
vertexSize++;
return true;
}
public boolean addEdge(int vnum1, int vnum2, int weight) {
assert (vnum1 >= 0 && vnum2 >= 0 && vnum1 != vnum2 && weight >= 0);
//有向图
if (graphType) {
edgesMatrix[vnum1][vnum2] = weight;
} else {
edgesMatrix[vnum1][vnum2] = weight;
edgesMatrix[vnum2][vnum1] = weight;
}
return true;
}
public void testWeight() throws Exception {
GraphByMatrix graph = new GraphByMatrix(Graph.UNDIRECTED_GRAPH, Graph.ADJACENCY_MATRIX, 6);
graph.addVertex("1");
graph.addVertex("2");
graph.addVertex("3");
graph.addVertex("4");
graph.addVertex("5");
graph.addVertex("6");
graph.addEdge(0, 1,7);
graph.addEdge(0, 2,9);
graph.addEdge(0, 5,14);
graph.addEdge(1, 3,15);
graph.addEdge(1, 2,10);
graph.addEdge(2, 3,11);
graph.addEdge(2, 5,2);
graph.addEdge(3, 4,6);
graph.addEdge(4, 5,9);
graph.Dijkstra(0);
System.out.println();
graph.Dijkstra("1");
System.out.println();
graph.Dijkstra2(0);
System.out.println();
}
}
第二种写法：
package com.android.test.demo.graph;
import android.util.ArrayMap;
import android.util.Log;
import com.google.common.graph.ElementOrder;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;
import java.util.Map;
import java.util.Set;
/**
* Created by tech on 18-1-11.
*/
public class Dijkstra {
private final static String TAG = "Dijkstra";
private static final String V0 = "v0";
private static final String V1 = "v1";
private static final String V2 = "v2";
private static final String V3 = "v3";
private static final String V4 = "v4";
private static final String V5 = "v5";
private static final String A = "A";
private static final String B = "B";
private static final String C = "C";
private static final String D = "D";
private static final String E = "E";
public static void test() {
MutableValueGraph<String, Integer> graph = buildGraph1();
Log.i(TAG, "graph: " + graph);
testDijkstra(graph, V0);
MutableValueGraph<String, Integer> graph2 = buildGraph2();
Log.i(TAG, "graph: " + graph2);
testDijkstra(graph2, A);
}
private static void testDijkstra(MutableValueGraph<String, Integer> graph, String startNode) {
Set<String> nodes = graph.nodes();
Map<String, NodeExtra> nodeExtras = new ArrayMap<>(nodes.size());
/**
* 初始化extra
*/
for (String node : nodes) {
NodeExtra extra = new NodeExtra();
extra.nodeName = node;
/*初始最短路径：存在边时，为边的权值；没有边时为无穷大*/
final int value = graph.edgeValueOrDefault(startNode, node, Integer.MAX_VALUE);
extra.distance = value;
extra.visited = false;
if (value < Integer.MAX_VALUE) {
extra.path = startNode + " -> " + node;
extra.preNode = startNode;
}
nodeExtras.put(node, extra);
}
/**
* 一开始可设置开始节点的最短路径为0
*/
NodeExtra current = nodeExtras.get(startNode);
current.distance = 0;
current.visited = true;
current.path = startNode;
current.preNode = startNode;
/*需要循环节点数遍*/
for (String node : nodes) {
NodeExtra minExtra = null;
int min = Integer.MAX_VALUE;
/**
* 找出起始点当前路径最短的节点
*/
for (String notVisitedNode : nodes) {
NodeExtra extra = nodeExtras.get(notVisitedNode);
if (!extra.visited && extra.distance < min) {
min = extra.distance;
minExtra = extra;
}
}
/**
* 更新找到的最短路径节点的extra信息（获取的标志、路径信息）
*/
if (minExtra != null) {
minExtra.visited = true;
minExtra.path = nodeExtras.get(minExtra.preNode).path + " -> " + minExtra.nodeName;
current = minExtra;
}
/**
* 并入新查找到的节点后，更新与其相关节点的最短路径中间结果
* if (D[j] + arcs[j][k] < D[k]) D[k] = D[j] + arcs[j][k]
*/
Set<String> successors = graph.successors(current.nodeName); //只需循环当前节点的后继列表即可
for (String notVisitedNode : successors) {
NodeExtra extra = nodeExtras.get(notVisitedNode);
if (!extra.visited) {
final int value = current.distance + graph.edgeValueOrDefault(current.nodeName,
notVisitedNode, 0);
if (value < extra.distance) {
extra.distance = value;
extra.preNode = current.nodeName;
}
}
}
}
/**
* 输出起始节点到每个节点的最短路径以及路径的途径点信息
*/
Set<String> keys = nodeExtras.keySet();
for (String node : keys) {
NodeExtra extra = nodeExtras.get(node);
if (extra.distance < Integer.MAX_VALUE) {
Log.i(TAG, startNode + " -> " + node + ": min: " + extra.distance
+ ", path: " + extra.path);
}
}
}
private static class NodeExtra {
public String nodeName; //当前的节点名称
public int distance; //开始点到当前节点的最短路径
public boolean visited; //当前节点是否已经求的最短路径
public String preNode; //前一个节点名称
public String path; //路径的所有途径点
}
private static MutableValueGraph<String, Integer> buildGraph1() {
MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed()
.nodeOrder(ElementOrder.insertion())
.expectedNodeCount(10)
.build();
graph.putEdgeValue(V0, V2, 10);
graph.putEdgeValue(V0, V4, 30);
graph.putEdgeValue(V0, V5, 100);
graph.putEdgeValue(V1, V2, 5);
graph.putEdgeValue(V2, V3, 50);
graph.putEdgeValue(V3, V5, 10);
graph.putEdgeValue(V4, V3, 20);
graph.putEdgeValue(V4, V5, 60);
return graph;
}
private static MutableValueGraph<String, Integer> buildGraph2() {
MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed()
.nodeOrder(ElementOrder.insertion())
.expectedNodeCount(10)
.build();
graph.putEdgeValue(A, B, 10);
graph.putEdgeValue(A, C, 3);
graph.putEdgeValue(A, D, 20);
graph.putEdgeValue(B, D, 5);
graph.putEdgeValue(C, E, 15);
graph.putEdgeValue(C, B, 2);
graph.putEdgeValue(D, E, 11);
return graph;
}
private static <K, V> String format(Map<K, V> values) {
StringBuilder builder = new StringBuilder();
builder.append("{");
Set<K> keys = values.keySet();
for (K key : keys) {
builder.append(key).append(":")
.append(values.get(key)).append(",");
}
if (builder.length() > 1) {
builder.deleteCharAt(builder.length() - 1);
}
builder.append("}");
return builder.toString();
}
private static <T> String format(Iterable<T> iterable) {
StringBuilder builder = new StringBuilder();
builder.append("{");
for (T obj : iterable) {
builder.append(obj).append(",");
}
if (builder.length() > 1) {
builder.deleteCharAt(builder.length() - 1);
}
builder.append("}");
return builder.toString();
}
}
Floyde
- 动态规划算法
public class Floyd {
private static final String TAG = "Floyd";
public static void test() {
int vexCount = 4;
int[][] arcs = new int[vexCount + 1][vexCount + 1];
int[][] path = new int[vexCount + 1][vexCount + 1];
/**
* 初始化图的邻接矩阵
*/
for (int i = 1; i <= vexCount; i++) {
for (int j = 1; j <= vexCount; j++) {
if (i != j) {
arcs[i][j] = Integer.MAX_VALUE;
} else {
arcs[i][j] = 0;
}
path[i][j] = j;
}
}
/**
* 输入图的边集
*/
arcs[1][2] = 2;
arcs[1][3] = 6;
arcs[1][4] = 4;
arcs[2][3] = 3;
arcs[3][1] = 7;
arcs[3][4] = 1;
arcs[4][1] = 5;
arcs[4][3] = 12;
print(arcs, vexCount, 0);
/**
* floyd核心算法：
* if arcs[i][k] + arcs[k][j] < arcs[i][j] then
* arcs[i][j] = arcs[i][k] + arcs[k][j]
*/
for (int k = 1; k <= vexCount; k++) {
for (int i = 1; i <= vexCount; i++) {
for (int j = 1; j <= vexCount; j++) {
if (arcs[i][k] < Integer.MAX_VALUE && arcs[k][j] < Integer.MAX_VALUE) {
final int d = arcs[i][k] + arcs[k][j];
if (d < arcs[i][j]) { //经过k点时i到j的距离比不经过k点的距离更短
arcs[i][j] = d; //更新i到j的最短距离
path[i][j] = path[i][k]; //更新i到j经过的最后一个点为k点
}
}
}
}
print(arcs, vexCount, k);
}
printPath(arcs, path, vexCount);
}
private static void print(int arcs[][], int vexCount, int index) {
Log.d(TAG, "print array step of " + index + ":");
for (int i = 1; i <= vexCount; i++) {
StringBuilder builder = new StringBuilder();
for (int j = 1; j <= vexCount; j++) {
if (arcs[i][j] < Integer.MAX_VALUE) {
builder.append(String.format("%5d", arcs[i][j])).append(" ");
} else {
builder.append(String.format("%5s", "∞")).append(" ");
}
}
builder.append("\n");
Log.d(TAG, builder.toString());
}
}
private static void printPath(int arcs[][], int path[][], int vexCount) {
Log.d(TAG, "print path:");
int temp;
for (int i = 1; i <= vexCount; i++) {
StringBuilder builder = new StringBuilder();
for (int j = 1; j <= vexCount; j++) {
builder.append(i).append("->").append(j)
.append(", weight: "). append(arcs[i][j]).append(":").append(i);
temp = path[i][j];
while(temp != j) {
builder.append("->").append(temp);
temp = path[temp][j];
}
builder.append("->").append(j).append("\n");
}
Log.d(TAG, builder.toString());
}
}
}
网友评论