implemented Floyd algorithm, but wondered how to do in addition to the output of the matrix of the shortest paths,
Even the output of the distance matrix that shows through what points it is necessary to go through the shortest path. (Example What does the distances matrix look like on the screen)

# include & lt; iostream & gt;
Using Namespace STD;
Int ** MAS = NULL;
int kol = 0;
// Calculating the minimum path on Floyd
void minfl (int ** m, int kl)
{
  For (int k = 0; k & lt; kl; k ++) {
      For (int i = 0; i & lt; kl; i ++) {
      For (int j = 0; j & lt; kl; j ++) {
        if (m [i] [j] & gt; m [i] [k] + m [k] [j])
        {
          m [i] [j] = m [i] [k] + m [k] [j];
        }
      }
    }
  }
}
INT MAIN ()
{
  SetLocale (LC_ALL, "RU");
  COUT & LT; & LT; "Enter the number of vertices of the graph" & lt; & lt; Endl;
  CIN & GT; & GT; kol;
  if (kol & lt; 1) {
    Return 0;
  }
  MAS = new int * [kol];
  for (int i = 0; i & lt; kol; i ++) mas [i] = new int [kol];
  COUT & LT; & LT; "Enter the arrangement matrix of the graph:" & lt; & lt; Endl;
  for (int i = 0; i & lt; kol; i ++)
    for (int j = 0; j & lt; kol; j ++) CIN & GT; & gt; MAS [i] [J];
  minfl (MAS, KOL);
  COUT & LT; & LT; "The minimum paths between the vertices:" & lt; & lt; Endl;
  for (int i = 0; i & lt; kol; i ++) {
    For (int j = 0; j & lt; kol; j ++) {
      COUT & LT; & LT; Mas [i] [j] & lt; & lt; "";
    }
    COUT & LT; & LT; Endl;
  }
  Return 0;

Answer 1, Authority 100%

Create an array for the best neighbors of the same size.

In the if statement unit>near the m [i] update [J] add

best [i] [j] = Best [i] [k]

At the end of the main algorithm for this pair of vertices a, b Go from Best [A] [b] until you do B .

Explanation: Best [A] [b] Stores the vertex to which you need to go from the vertex a to reach B optimally. If we moved to the top of with , now Best [C] [b] stores the top to which you need to go from the vertex with to achieve b optimally.

Starting Initialization Best – For each vertex Best [A] [A] = A , for the edge AB Best ] [b] = b , the rest is filled with special design (for example, -1)

Wiki