简介

欢迎回到图算法系列！到目前为止，所有边的权重都相同。现在边带有权重（成本或距离），我们要找到成本最低的路线。

Dijkstra 算法可以在边权重非负的图中，找出从单个源点到每个其他顶点的最短距离。

带权图表示为 n（顶点编号从 0 到 n - 1）和 edges，后者是由三元组组成的一维数组 [u0, v0, w0, u1, v1, w1, ...]，其中每个三元组表示一条权重为 w 的有向边 u -> v。

开始吧！