要计算非加权图中的最短路径, 可使用广度优先搜索。 要计算
加权图中的最短路径,可使用狄克斯特拉算法。
在无向图中,每条边都是一个环。狄克斯特拉算法只适用于有向无环图
以下是具体的算法实现
/**
* 广度优先算法适用于无权边计算最短路径
* 狄克斯特拉算法适用于有权边计算最短路径
* 仅当权重为正时才适用
* 如果权重为负,应使用贝尔曼-福德算法
*
*/
package com.algorithm.kavin;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Dijkstra {
// 用于记录处理过得node
private static List<String> processed = new ArrayList<>();
// 创建graph所在map
private static Map<String, Map<String, Integer>> graph = new HashMap<>();
public static String findSmallerNode(Map<String, Integer> cost) {
int smallerCost = Integer.MAX_VALUE;
String smallerCostNode = null;
for (String key : cost.keySet()) {
int tempCost = cost.get(key);
if (tempCost < smallerCost && !processed.contains(key)) {
smallerCost = tempCost;
smallerCostNode = key;
}
}
return smallerCostNode;
}
public static void main(String[] args) {
graph.put("start", new HashMap<>());
graph.get("start").put("A", 6);
graph.get("start").put("B", 2);
graph.put("A", new HashMap<>());
graph.get("A").put("fin", 1);
graph.put("B", new HashMap<>());
graph.get("B").put("A",3);
graph.get("B").put("fin", 1);
graph.put("fin", new HashMap<>());
// 创建cost消耗所在map
Map<String, Integer> costs = new HashMap<>();
costs.put("A", 6);
costs.put("B", 2);
costs.put("fin", Integer.MAX_VALUE);
// 创建父节点
Map<String, String> parent = new HashMap<>();
parent.put("A", "start");
parent.put("B", "start");
parent.put("fin", null);
// 开始处理问题
String smallestNode = findSmallerNode(costs);
while (smallestNode != null) {
Integer cost = costs.get(smallestNode);
Map<String, Integer> neighbour = graph.get(smallestNode);
for (String i : neighbour.keySet()) {
Integer newCost = cost + neighbour.get(i);
if (costs.get(i) > newCost) {
costs.put(i, newCost);
parent.put(i, smallestNode);
}
}
processed.add(smallestNode);
smallestNode = findSmallerNode(costs);
}
System.out.println(graph);
}
}