Dijkstra Algorithm基本过程与理解
Series S2: 求一点出发到一点/其他所有点的最短路径
使用条件：边上的权证可以有且不相同但必须为正值
Series S1:讲了五个series（见前面的shortest path）
Use Case 1:求出一个点到一个点的最短路径
什么是Dijkstra Algorithm? Best First Search VS Dijkstra
Dijkstra：需要有一个Starting Node（题目给的），每一次从到目前为止Cost最低的点出发（Expand），generate所有它的邻居，直到我们Expand到targetNode/所有Node为止！
每当一个点被Expand的时候，它的最短路径（从start到他）就确定了
注意expand& generate
expand表示你接下来要访问的
所以你一旦访问了，就表示确定了，所以对于dijkstra来说，每次要访问的(expand)，一旦他被访问了，从源头点到该点的最短就确定了
如果记录的每点cost最小，也就是costMark(x) = min Cost(源头，x)
min cost（源头，x）= minCost （源头，y） + minCost（y，x）
这个成立的唯一条件，就是cost是正的&cost函数是monotonicity increasing的？
generate表示你potential需要访问的点
Greedy算法
不看所有解，我觉得按着某一种方法（aha point）去走，我就得到最优解
Greedy算法需要证明，也需要一些灵感！
反证法：会不会有一个被expand的点，其实从源点到它的最短路径没有确定，会在后面的expansion来确定
被Generate的点， A(13), B(15), D(17)
Expansion： dis(Src, first_time_C) = 10
dis(Src, second_expanded_C) = initial dis from src to the cur node(>= 10) + dis of all the path behind
dis(Src, second_expanded_C) > dis(Src, first_time_C)
假设错误
在Dijsktra算法中需要注意
明确你的cost是什么
我们允许一个点被Generate多次，先generate的不一定是最短路径（时间最先！=cost最优）
在有权重图中，Mark Visited at Generation是不一定正确的！！
Cost of Neighbor When Generation
dis(src, nei) = dis(src, cur) + weight of (cur, nei)
General Implementation for Dijkstra
class GraphNode{
String node;
int weight;
public GraphNode(String node, int weight) {
this.node;
this.weight;
}
}
public int findShortestPath(String start, String end, Map<String, List<GraphNode>> graph) {
// mapping for node and index
Map<String, Integer> nodeToIndex = new HashSet<>(); //这个Map可以不要，根据你的构图决定
int index = 0;
for (String node: graph.keySet()) {
nodeToIndex.put(node, index++);
}
int n = graph.size(); //有几个node
int[] distances = new int[n]; //这个是记录node的对应的distance //有点像dp
Arrays.fill(distances, Integer.MAX_VALUE); //现在把distance全部记录最大
boolean[] visited = new boolean[];
distance[nodeToIndex.get(start)] = 0;
//至多node轮
for (int i = 0; i < n - 1; i++) { //明确告诉你Dijkstra最多有多少轮
int uIndex = selectMinimumIndex(distances, visited); // 从当前cost最低点出发// 这部分可以被pq优化
visited[uIndex] = true; // u 是个index不是这个点,所以你要反向找回那个node
for (GraphNode v: graph.getOrDefault(indexToNode(uIndex, nodeToIndex), new ArrayList<>())) {
int vIndex = nodeToIndex.get(v.node);
if (!visited[vIndex] && distances[uIndex] != Integer.MAX_VALUE && distances[uIndex] + v.weight < distance[vIndex]) {
distances[vIndex] = distance[uIndex] + v.weight;
}
}
}
return distances[nodeToIndex.get(end)];
}
private String indexToNode(int index, Map<String, Integer> nodeToIndex) {
for (Map.Entry<String, Integer> entry: nodeToIndex.entrySet()) {
if (entry.getValue().equals(index)) {
return entry.getKey();
}
}
return null;
}
private int seletecMinimumIndex(int[] distances, boolean[] visited) {
int minIndex = -1;
int minValue = Integer.MAX_VALUE;
for (int i = 0; i < distance.length; i++) {
if (!visited[i] && distances[i] < minValue) {
minValue = distance[i];
minIndex = i;
}
}
return minIndex;
}这个array版本的实现
缺点：时间肯定不如现代版本的heap/treeMap/treeSet版本实现
优点：元和可读性以及区分性: already_expanded & already_generated
if (distances[uIndex] + v.weight < distances[vIndex]) {distances[vIndex] = distance[uIndex] +v.weight};
在这个视线里面，如果一个点被generate多次，不管后面的generate比前面generate得到的结果好还是坏
distances[i]只要visited是false i的状态都是already_generated but not yet expand。存储的只会是最优解，一旦visited[i] mark成为true了，说明被expanded
General Implementation for Dijkstra 现代版
class GraphNode{
String label;
int cost;// 到目前为止的cost，src到这个node的距离和
public GraphNode(String label, int cost) {
this.label;
this.cost;
}
}
public int findShortestPath(String start, String end, Map<String, List<GraphNode>> graph) {
if (start.equals(end)) return 0;
PriorityQueue<GraphNode> minHeap = new PriorityQueue<> ((node1, node2) -> .compare(node1.cost, node2.cost));
Map<String, Integer> shortestPath = new HashMap<>(); //这个其实是你mark Visited，这里把mark和map合起来了嘛。。
minHeap.offer(new GraphNode(Sstart, 0));
while (!minHeap.isEmpty()) {
GraphNode currentNode = minHeap.poll();
String currentLabel = currentNode.label;
int currentCost = currentNode.cost;
// 第一次exapnd到target就可以结束了，上面的实现没有加
if(currentLabel.equals(end)) {
return currentCost;
}
// 已经expand过的点不再expand
if (shortestPath.containsKey(currentLabel)) {
continue;
}
shortestPath.put(currentLabel, currentCost);
for(GraphNode neighbor: graph.getOrDefualt(currentLabel, new ArrayList<>()) {
String neighborLabel = neighbor.label;
int totalCostToNeighbor = currentCost + neighbor.cost;
// given graph 初始化cost储存的是weight
if (!shortestPath.containsKey(neighborLabel)) {
minHeap.offer(new GraphNode(neighborLabel, totalCostToNeighbor));
}
/*
其实可以完全分开
case 1: neighbor node 已经被expand过了
无视
case 2: neighbor node虽然没有被exapnd过， 被generate过了
Map<Node, Integer> already_generateMap: <Node, 上一次generate的cost>
如果这一次generate的totalCostToNeighbor比上一次低才generate
case 3: 这个node还没有被generate过
直接generate
*/
}
return -1;
}Quesiton: 我能不能对于这种被generate的点，直接在PriorityQueue里更新的Entry？
不行，但是可以进行如下操作
优化Java PQ: Search + update: 除非自己实现PriorityQueue, MappedPriorityQueue
选择TreeSet/ TreeMap update: remove + insert
TC&SC
TC:普通的遍历算法O(|V| + |E|) ==> O((|V| +|E|) * log |E|)
Dijkstra: O(|V+E| * log(E))
除非你做了generation的优化，我保证了每个点至多被generate一次O((V+E)log(V))
SC: O(E) or O(V) if you optimize for generation
Use Case 2: 求出从一个点到所有点的最短路径
shortestPaths 里其实存的就是每一个点的最短路径值，而我们只要把遇到target node就return的这个限制条件去掉就好
Use Case 3: Dijkstra在面试中的难点: Multiple-Dimension Node
Example
告诉你地图中所有城市的道路，求从一个start城市出发，走exactly K步能哦租到的所有城市中，总距离和距离当前城市最近的城市
graph representation？明白什么是点，什么是边，每个点能去哪些点
为什么不用这个edge不好用，因为没法快速的知道，每个点能去哪些点
比较好的表达方式 adjacency list
Map<Node, Map<Node, Integer>> weightGraph
Map<Node, List<Node>> unidirectedGraph
小心
走exactly K步能得到的距离和最小 不等与
first time走k步的city，因为可能还有些点没有看到
K步之内的距离和最小，因为这里说的是我要走K步呀
思考：说白了，因为dijkstra解决的是，某个点，到某个点的最短路径，但是这里的问题没有给出到底到哪个点的？——》所以你就都看step = K——》让每次expand出来的点的step是排好序的
多维度问题的关系
如果你保证，Expand点或者generate点的顺序是单调的，就可以在第一次遇到它就终止算法
如果你能保证你generate点的时候，从小到达的单调递增的来generate，甚至可以在generate mark visited
如果你能保证你expand点的顺序是单调的，那就可以在第一次expand到他的时候终止
Summary
Dijkstra算法中每exapnd一次，就确定了从点A到点B的最短路径，往后只能增大不能减少！如果求的是从一个点到所有点的最短路径，也只需要做一次！One to ALL！
是否可以在Generate的时候Mark Visited：不一定
时空复杂度: O(|V| +|E|) log(|E|)
每个点允许被generate多次但是最多只能被expand一次
如果我们自己实现MappedPriorityQueue，那么可以实现Node只能被Generated一次，但是非常复杂情况不如用TreeMap/TreeSet代替更为简洁
MappedPriortyQueue：Use case是我们遇到一个已经generated的点的时候，Map找到Node Position，UpdatedValue +上下调整
Last updated