求问这道图的题怎么做

谢谢大家！

就是最短路径吧，只就图类问题来说算基本题吧，在面试里肯定是hard了。

这题因为是single source到all nodes的最短路径，可以用bellman-ford做。
当然上面提到的dijkstra也是可以的，就把每一个node作为destination，各跑一遍dijkstra，取最大值就好了。毕竟掌握dijkstra的性价比比bellman-ford高很多。

这题特意强调了是个sparse graph，不知道有没有啥tricky的地方在具体implementation上。

SSSP
.
https://en.wikipedia.org/wiki/Sh ... urce_shortest_paths

337845818 发表于 2019-9-29 03:36
SSSP
.
https://en.wikipedia.org/wiki/Sh ... urce_shortest_paths

SSSP是什么

liujiayi0531 发表于 2019-9-29 04:22
SSSP是什么

https://en.wikipedia.org/wiki/Sh ... urce_shortest_paths

lc743 好像是dijkstra做

gatechkc 发表于 2019-9-29 14:44
lc743 好像是dijkstra做

哇厉害厉害，我去看看，743对我来说好遥远

dijkstra 最短路径，直到遍历完所有可能节点。同时计数可到达的节点数目，如果最后可到达数目小于节点数目，null。