深圳营销型网站费用,可以在哪些网站 APP做推广,响应式全屏网站模板,做摄影网站公司A good way to think about Dijkstra is:Dijkstra works when the first time you remove a node from the priority queue, you already know its optimal value.This is called the greedy property. If a nodes val… A good way to think about Dijkstra is:Dijkstra works when the first time you remove a node from the priority queue, you already know its optimal value.This is called the greedyproperty. If a node's value can still improve later by taking a different path, Dijkstra is not applicable.Cases where Dijkstra works 1. Shortest Path (Classic) Edges represent distances.A --2-- B --3-- D\ ^\5 |v 1C ----Suppose we're finding the shortest path from A. InitiallyA = 0 B = 2 C = 5We pop B first because 2 5. Could there later be another path to B shorter than 2? No. Any other path must go through C, whose distance is already ≥5. So2 + positive edge 2Impossible to improve. This is exactly why Dijkstra works. Requirement:edge weights ≥ 02. Network LatencyRouter A| 10ms| Router B| 5ms| Router CTotal latency10 + 5 = 15msAgain,weights are nonnegative costs only increasePerfect for Dijkstra.3. GPS Navigation Road lengthsRoad1 = 5 km Road2 = 8 km Road3 = 2 kmDistance always accumulates positively. Works.4. Cheapest Flight (without discounts) EdgeA - B = $100Cost100 + 80 + 50Again additive positive cost. Works.5. Maximum Bottleneck Path (modified Dijkstra) Suppose bandwidthsA --10-- B --8-- D A --20-- C --5-- DPath capacity ismin(edge capacities)SoA-B-D = 8 A-C-D = 5We maximize the minimum. A modified Dijkstra works becausecapacity(path) = min(previous_capacity, edge)The capacity never increases after extending a path. The greedy property still holds.Cases where Dijkstra does NOT work 1. Negative EdgesA --2-- B A --5-- C C --(-10)-- BInitiallyB = 2 C = 5Dijkstra popsBBut laterA - C - B 5 + (-10) = -5Much better. Too late. Greedy fails. Bellman-Ford is needed.2. Currency Exchange (your problem)A - B = 2 A - C = 10 C - B = 0.5ProductsA-B 2vsA-C-B 10 × 0.5 =5NoticeBlooked optimal initially2but later became5Dijkstra finalized B too early.3. Longest Path SupposeA - B = 2 A - C = 1 C - B = 100Longest pathA-B 2vsA-C-B 101AgainBlooked finished but wasn't.4. Maximum Product Exactly your interview problem.rate *= edgeProducts may increase dramatically later. Greedy property breaks.5. Paths with Rewards Imagineedge cost = travel timenode reward = moneyObjectivemaximize reward - costReaching a node cheaply isn't necessarily best if another path collects much more reward. No greedy property.A useful rule of thumb Suppose your path value isnewValue = combine(oldValue, edge)Ask:Can extending a worse path ever make it better than a currently better path?If the answer is No, Dijkstra usually works. If Yes, Dijkstra usually fails.Works Sumnew = old + edgewithedge ≥ 0Cannot decrease. Works.Minimumnew = min(old, edge)Cannot increase. Works.Maximumnew = max(old, edge)Cannot decrease in the relevant direction. Works.Doesn't work Productnew = old * edgebecause10 × 0.1 = 12 × 100 = 200A worse partial product2can become200while the better one10becomes1Ordering changes.Sum with negative edges2 + (-10) = -8A worse partial sum can become better. Ordering changes.Interview heuristic When solving a graph problem, ask these questions:Is the objective additive?distance += edge cost += edge time += edge → Think Dijkstra.Are all edge "increments" non-negative?If not, Dijkstra is unsafe.Can the ranking of two partial paths flip after extending them?For example, suppose two paths reach different nodes with current values:Path 1: value = 10 Path 2: value = 2If after one more edge you can get:Path 1 - 1 Path 2 - 200then the ordering has flipped. Once this can happen, the greedy assumption behind Dijkstra no longer holds, and you should be suspicious of using it. This "can the ordering flip?" test is one of the quickest ways to judge whether Dijkstra is appropriate in an interview.