Изменения

* Глубиной вершины <tex>v\in T_{x}</tex>, где <tex>T_{x}</tex> - частично обработанное дерево с корнем в <tex>x</tex> величину <tex>depth(v)=d(v)+in\textrm{--}penalty(x)</tex> , где <tex>d(v)</tex> - длина пути от корня до вершины в дереве.* Чтобы определить высоту вершины, нам нужно понятие "ложных листьев". Для каждой вершины <tex>v</tex> в дереве кратчайших путей добавим потомка <tex>v'</tex> - ложный лист, и ребро <tex>(v,v') = out\textrm{--}penalty(v)</tex>. В некотором смысле, <tex>v'</tex> будет выступать в роли всех рёбер, изначально инцидентных вершине <tex>v</tex>, которые мы отсекли. Тогда высотой вершины <tex>v</tex> будет расстояние от неё, до наиболее далёкого ложного листа. Подчеркнём, что в данный момент ложные листья добавляются неявно, и только после того, как дерево будет частично обработано.