Home c++ Floyd algorithm, output of the distance matrix

# Floyd algorithm, output of the distance matrix

Author

Date

Category

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;
`````` 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

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.