用弗洛伊德算法求两点之间最短路径

Question

/*设计算法以求解从vi到vj之间的最短路径。（每条边的长度为1）
*/
#include<iostream>
using namespace std;
#define max 1000
#define INF 65535
typedef char element;
typedef int cellType;
typedef enum { UDG, UDN, DG, DN }GraphKind;//枚举图的类型
typedef struct GraphAdjMatrix {
    element data[max];//顶点数组，存放顶点元素的值,从0开始
    cellType AdjMatrix[max][max];//邻接矩阵，元素类型为cellType
    int verNum;//顶点数
    int arcNum;//弧数
    GraphKind gkind;//图的类型，0-无向图，1-无向网，2-有向图，3-有向网
}Graph;//图的类型名
//Floyd算法描述
 //删除字符串、字符数组左边空格
void strLTrim(char* str)
{
    int i, j;
    int n = 0;
    n = strlen(str) + 1;
    for (i = 0; i < n; i++)
    {
        if (str[i] != ' ')  //找到左起第一个非空格位置
            break;
    }
    //以第一个非空格字符为手字符移动字符串
    for (j = 0; j < n; j++)
    {
        str[j] = str[i];
        i++;
    }
}

//从数据文件创建邻接矩阵表示的图
int CreateGraphFromFile(Graph*& G)
{
    FILE* pFile;          //定义文件指针
    char str[1000];         //存放读出一行文本的字符串
    char strTemp[10];      //判断是否注释行
    cellType eWeight;      //边的信息，常为边的权值
    GraphKind graphType;  //图类型枚举变量
    errno_t err;
    err = fopen_s(&pFile, "D:\\数据结构代码\\图的文本文件\\dn10.grp", "r");
    if (!pFile)
    {
        cout << "错误：文件打开失败。" << endl;
        return false;
    }
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);     //删除字符串左边空格，这是一个自定义的函数
        if (str[0] == '\n')    //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, sizeof(strTemp), str, 2);
        if (strstr(strTemp, "//") != NULL)  //跳过注释行
            continue;
        else                       //非注释行、非空行，跳出循环
            break;
    }
    //循环结束，str中应该已经是图的标识Graph，判断标识是否正确
    if (strstr(str, "Graph") == NULL)
    {
        cout << "错误：打开的文件格式错误！ " << endl;
        fclose(pFile); //关闭文件
        return false;
    }
    //读取图的类型，跳过空行
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);    //删除字符串左边空格，这是一个自定义函数
        if (str[0] == '\n')   //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, sizeof(strTemp), str, 2);
        if (strstr(strTemp, "//") != NULL)  //注释行，跳过，继续读取下一行
            continue;
        else                       //非空行，也非注释行，即图的类型标识
            break;
    }
    //设置图的类型
    if (strstr(str, "UDG"))
        graphType = UDG;    //无向图
    else if (strstr(str, "UDN"))
        graphType = UDN;    //无向网
    else if (strstr(str, "DG"))
        graphType = DG;     //有向图
    else if (strstr(str, "DN"))
        graphType = DN;     //有向网
    else
    {
        cout << "错误：读取图的类型标记失败！ " << endl;
        fclose(pFile);       //关闭文件
        return false;
    }
    //读取顶点行数据到str。跳过空行
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);      //删除字符串左边空格，这是一个自定义函数
        if (str[0] == '\n')     //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, sizeof(strTemp), str, 2);
        if (strstr(strTemp, "//") != NULL)  //注释行，跳过，继续读取下一行
            continue;
        else                       //非空行，也非注释行，即图的顶点元素行
            break;
    }

    //顶点数据放入图的顶点数组    
    char* ptr = NULL;
    char* token = strtok_s(str, " ", &ptr);
    int nNum = 0;
    while (token != NULL)
    {
        G->data[nNum] = *token;
        token = strtok_s(NULL, " ", &ptr);
        nNum++;
    }
    //图的邻接矩阵初始化
    int nRow = 0;    //矩阵行下标
    int nCol = 0;     //矩阵列下标
    if (graphType == UDG || graphType == DG)
    {
        for (nRow = 0; nRow < nNum; nRow++)
            for (nCol = 0; nCol < nNum; nCol++)
                G->AdjMatrix[nRow][nCol] = 0;
    }
    else
    {
        for (nRow = 0; nRow < nNum; nRow++)
            for (nCol = 0; nCol < nNum; nCol++)
                G->AdjMatrix[nRow][nCol] = INF;  //INF表示无穷大
    }
    //循环读取边的数据到邻接矩阵
    int edgeNum = 0;         //边的数量
    element  Nf, Ns;     //边或弧的2个相邻顶点
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);       //删除字符串左边空格，这是一个自定义函数
        if (str[0] == '\n')      //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, sizeof(strTemp), str, 2);
        if (strstr(strTemp, "//") != NULL)  //注释行，跳过，继续读取下一行
            continue;
        char* ptr = NULL;
        char* token = strtok_s(str, " ", &ptr);
        if (token == NULL)         //分割为空串，失败退出
        {
            cout << "错误：读取图的边数据失败！ " << endl;
            fclose(pFile);         //关闭文件
            return false;
        }
        Nf = *token;               //获取边的第一个顶点
        token = strtok_s(NULL, " ", &ptr);   //读取下一个子串，即第二个顶点
        if (token == NULL)          //分割为空串，失败退出
        {
            cout << "错误：读取图的边数据失败！ " << endl;
            fclose(pFile);          //关闭文件
            return false;
        }
        Ns = *token;  //获取边的第二个顶点
                 //从第一个顶点获取行号        
        for (nRow = 0; nRow < nNum; nRow++)
        {
            if (G->data[nRow] == Nf)  //从顶点列表找到第一个顶点的编号
                break;
        }
        //从第二个顶点获取列号
        for (nCol = 0; nCol < nNum; nCol++)
        {
            if (G->data[nCol] == Ns)  //从顶点列表找到第二个顶点的编号
                break;
        }
        //如果为网，读取权值
        if (graphType == UDN || graphType == DN)
        {                //读取下一个子串，即边的附加信息，常为边的权重
            token = strtok_s(NULL, " ", &ptr);
            if (token == NULL)    //分割为空串，失败退出
            {
                cout << "错误：读取图的边数据失败！ " << endl;
                fclose(pFile);    //关闭文件
                return false;
            }
            eWeight = atoi(token);  //取得边的附加信息
        }
        if (graphType == UDN || graphType == DN)
            G->AdjMatrix[nRow][nCol] = eWeight;
        //如果为网，邻接矩阵中对应的边设置权值，否则置为1
        else
            G->AdjMatrix[nRow][nCol] = 1;
        edgeNum++;   //边数加1
    }
    G->verNum = nNum;           //图的顶点数
    if (graphType == UDG || graphType == UDN)
        G->arcNum = edgeNum / 2;  //无向图或网的边数等于统计的数字除2  
    else
        G->arcNum = edgeNum;
    G->gkind = graphType;         //图的类型
    fclose(pFile);               //关闭文件
    return true;
}
 void Floyd(Graph*& G, cellType dist[max][max], int path[max][max]) {
    int i, j, m;
    for (i = 2; i <= G->verNum+1; i++) {//初始化距离矩阵和路径矩阵
        for (j = 2; j <= G->verNum+1; j++) {
//距离矩阵初始化为邻接矩阵
            dist[i - 1][j - 1] = G->AdjMatrix[i - 1][j - 1];
            //初始化路径矩阵，路径矩阵元素path[i-1][j-1],保存顶点编号j顶点的前驱的顶点编号
            //如果i,j之间存在边，则j的前驱为i,否则前驱置为-1
            if (i != j && G->AdjMatrix[i - 1][j - 1] < INF)
                path[i - 1][j - 1] = i;
            else
                path[i - 1][j - 1] = -1;
        }
     }
    //以下是三重for循环
    for (m = 2; m <=G->verNum+1; m++) {
        for (i = 2; i <= G->verNum+1; i++) {
            for (j = 2; j <= G->verNum+1; j++) {
                //m作为跳点，i,j之间距离变小，接收m作为中转点
                if (i != j && dist[i - 1][m - 1] + dist[m - 1][j - 1] < dist[i - 1][j - 1]) {
                    //更新最短距离
                    dist[i - 1][j - 1] = dist[i - 1][m - 1] + dist[m - 1][j - 1];
                    //更新路径
                    path[i - 1][j - 1] = path[m - 1][j - 1];
                }
            }
        }
    }
    
} 
 //打印两点最短路径
 void print(Graph*& G, cellType dist[max][max], int path[max][max]) {
     int u, v;
     cout << "输入想要求解最短路径的两点下标：";
     cin >> u >> v;
     int k = path[u][v];//k为v的前驱
     cout << G->data[u] << " ";//打印起点
     while (k != v) {
         cout << G->data[k] << " ";//打印中间点
         k = path[k][v];
     }
     cout << G->data[k];//打印终点
 }
int main() {
    Graph*G = new Graph();
     cellType dist[max][max] ;
    int path[max][max];
    Floyd(G,dist,path);
    print(G, dist, path);
    return 0;
}

这里已经new一个新空间了，为什么还说超出了

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7746957
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：数据结构与算法 —— 常用时间复杂度与空间复杂度
• 除此之外, 这篇博客: 桶排序之计数排序中的 2.new一个最大值大一的空间，并开始加数 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  代码如下（示例）：

  int []bucket = new int [max + 1];
  		for(int i = 0;i<arr.length;i++) {
  			
  			bucket[arr[i]]++;
  		}
  

• 您还可以看一下 CSDN讲师老师的如何从期权市场交易来挖掘市场多空情绪课程中的 如何从期权市场交易来挖掘市场多空情绪（上）小节, 巩固相关知识点
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^