L006 单源最短路

赋权图和距离

允许顶点和边有赋有「属性」的图称作「网络」（network）。

「赋权图」（weighted graph）是一个三元组，记作 \(G=\left\langle V,E,w\right\rangle\)，其中 \(V\) 是顶点的有限集合，\(E\) 是边的有限集合，\(w:E\to \mathbb{R}\) 是「赋权函数」（weight function），定义域是边集 \(E\)，陪域是实数集 \(\mathbb{R}\)，\(w(e)\) 称为边 \(e\) 的「权」（weight）。

拓展的邻接矩阵和关联矩阵、「赋权长度」/「长度」（weighted length）、最短路、距离、离心率、中心点、半径、中心、边缘点、直径。

「迪杰斯特拉算法」（Dijkstra's algorithm）、「贝尔曼-福特算法」（Bellman-Ford algorithm）

【Algo.6.1】

Th.6.1