MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A directed weighted graph has vertices s,a,b,ts,a,b,t and edges s→a:1s\to a{:}1, s→b:10s\to b{:}10, a→b:−8a\to b{:}-8, a→t:9a\to t{:}9, b→t:2b\to t{:}2, s→t:15s\to t{:}15. Since one weight is negative, Dijkstra's algorithm cannot be trusted here. What is the TRUE shortest path length from ss to tt, found by checking every route directly?