What does vector P mean in Dijkstra's algorithm?

Question

Algorithms

I read an excellent article about Dijkstra's algorithm:

https://habr.com/ru/post/111361/

At the end of the article, the vector P is mentioned.

What does this vector mean, why initially all its values ​​\u200b\u200bin the number of vertices are equal to 1 and what is the minimum path , for example, from vertex 1 to 4.

Answer 1

Вектор P, как написанно в статье - хранит для каждой вершины предыдущую в кратчайшем пути к ней. Грубо говоря, в каждой вершине у вас будет указатель на направление, откуда в эту вершину приходит кратчайший путь. Или, если вы развернете все пути, это будет указатель, куда идти, чтобы вернуться в начальную вершину.
Изначально его не обязательно заполнять еденицами. Там может быть что угодно. -1, например, как обозначение, что кратчайший путь для этой вершины пока не найден. Значение в начальной вершине - не важно, потому что оно не имеет смысла (вроде как направление на север на северном полюсе - вы уже там).
Переписываете вы эти значения только один раз, когда находите кратчайшее расстояние для какой-то вершины. В этот момент вы знаете, по какому ребру вы в нее придете и записываете начало этого ребра в вектор P для конца.
В примере Р = {1, 1, 5, 5, 1} означает, что для второй вершины кратчайший путь будет 1-2. Предыдущая вершина в пути к 2 - 1 (p[2]=1). Все. это уже начало пути.
Для вершины 3 предыдущая - 5 (потому что P[3] = 5). Значит путь к ней будет ..-5-3. Обратите внимание, пока мы знаем только, что путь заканчивается на 5-3. Пока мы не знаем, может между 1 и 5 что-то еще. Но, если мы посмотрим на P[5] - там записанна 1 - значит предыдущая в кратчайшем пути до 5 - уже 1. Вот и весь путь 1-5-3.
Еще пример для P={1,1,2,3} путь для 4 будет ..-.3-4, потому что P[4] = 3. Потом, P[3]=2, значит путь ...-2-3-4. Потом приписываем к пути P[2] и получаем 1-2-3-4. все, мы вернулись в изначальную вершину, можно остановится.
Путь воостановить довольно просто: заведите переменную v, которая будет указывать на текущую вершину в пути. Это будет изначально вершина, до которой вы хотите путь восстановить. Потом в цикле, пока не упретесь в начальную вершину, меняйте v на p[v]. Делайте, как бы, один шаг назад. При этом как-то запоминайте все вершины, по которым вы прошлись. Так вы построите кратчайший путь, только задом-наперед. его еще надо будет развернуть.
Обычно это делается как-то так:

vector<int> GetPath(const vector<int> &p, int be, int v) {
  vector<int> res;
  while (v != be) {
    res.push_back(v);
    v = p[v];
  }
  res.push_back(be);
  reverse(res.begin(), res.end());
  return res; 
}