文章

10

粉丝

179

获赞

5

访问

31.8k

头像
弗洛伊德算法求出各点间的最短距离和最佳路径
P1666 中南大学机试题
发布于2023年2月9日 20:26
阅读数 2.7k

#include <bits/stdc++.h>
using namespace std; 
typedef long long ll;
const int INF=1e9;
int n,m,S,T,A;
int mp[1001][1001];//存储图像
string path[1001][1001]; //以字符串的方式记录每个点之间的最佳路径
string name[1001];//记录顶点

void floyd(){                    //弗洛伊德函数
   
    for(int i=1;i<=n;i++){          //初始化path路径数组
        //path[i]=new string [n];
        for(int j=1;j<=n;j++){
            if(i==j) path[i][j]=name[i];
            else path[i][j]=name[i]+name[j];
        }
    }
    
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                
               if(mp[i][k]==INF || mp[k][j]==INF) continue;
                if(i!=j){
                    if(mp[i][j]==INF || mp[i][j]>mp[i][k]+mp[k][j]){
                    mp[i][j]=mp[i][k]+mp[k][j];        //计算单源最短路径
                    path[i][j]=path[i][k].substr(0,path[i][k].length()-1)+path[k][j]; //若i通过k到j的距离更短,则将i到k的路径的字符串与k到j的路径合并到一起,因为k是重复的,所以要减去一个k
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发