Постановка задачи

Пусть G = (V, E, W) – ориентированный граф без петель со взвешенными ребрами. Полагаем множество вершин V={1, … , n}, множество ребер E <= V*V, |E| = m и весовая функция W(u,v) каждому ребру (u, v)<=E ставит в соответствие  его вес – неотрицательное число. Требуется найти кратчайшие пути от заданной вершины s<=V до всех остальных вершин.

Если исходный граф не ориентирован, то следует превратить в ориентированный, заменив каждое его ребро {u,v} на два ребра (u,v) и (v,u) того же веса.

Решением задачи будем считать два массива:

  • массив dist[1..n], (dist[i] – кратчайшее расстояние от вершины s до вершины i).
  • массив up[1..n], (up[i] – предпоследняя вершина в построенном кратчайшем пути из вершины s в вершину i).

Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.