首页 > 代码库 > Floyd 算法 打印路径模板

Floyd 算法 打印路径模板

#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <cmath>#include <cstring>using namespace std;#define INF 0xfffffff#define maxn 40int G[maxn][maxn], Path[maxn][maxn], n;void Floyd(){    for(int k=1; k<=n; k++)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)            {                if(G[i][j] > G[i][k] + G[k][j])                {                    G[i][j] = G[i][k] + G[k][j];                    Path[i][j] = Path[i][k];                }            }        }    }}void PutPath(int Star,int End){    while(Star != End)    {        printf("%d---->", Star);        Star = Path[Star][End];    }    printf("%d\n", End);}void Init(){    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)        {            Path[i][j] = j;        }    }}int main(){    cin >> n;    Init();    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)        {            cin >> G[i][j];            if(G[i][j] == -1)                G[i][j] = INF;        }    }    Floyd();    PutPath(1,n);    printf("%d\n", G[1][n]);    return 0;}/*4-1 1 -1 -1-1 -1 1 -1-1 -1 -1 1-1 -1 -1 -1*/

 

Floyd 算法 打印路径模板