动态规划求解最短行驶路线问题[Floyd算法]

使用Qt做的演示程序~ 时间是大二下学期的算法分析实践环节。采用Floyd方法求解最短行驶路线问题。

#include “graph.h“

Graph::Graph（）
{
    MAX_INT = 999999;
}

void Graph::clear（）
{
    delete[] mat;

    for（int i=0; i    {
        delete[] dist[i];
        delete[] path[i];
    }
    delete[] path;
    delete[] dist;

    spath.clear（）;
    nodes.clear（）;
}

bool Graph::readFile（QString fileName）
{
    QFile f（fileName）;
    QFileInfo fileInfo;
    fileInfo.setFile（fileName）;
    if（fileInfo.suffix（）!= “map“）
        return false;

    if（!f.open（QIODevice::ReadOnly | QIODevice::Text））
    {
        qDebug（）<        return false;
    }

    QTextStream inStream（&f）;

    inStream.readLine（）;  // 舍弃注释行

    m = inStream.readLine（）.toInt（）; // 矩阵列数m
    n = inStream.readLine（）.toInt（）; // 矩阵行数n
    num = m*n;

    dist = new int*[num];
    path = new int*[num];
    for（int i=0; i    {
        dist[i] = new int[num];
        path[i] = new int[num];
    }

    /// 读入num个结点
    QStringList strList = inStream.readLine（）.split（QRegularexpression（“\\s+“））;

    for（int i=0; i    {
        Node newNode;
        newNode.nodeName =strList[i];
        newNode.pos = QPoint（i%ni/n）;  // 新结点的坐标

        nodes.push_back（newNode）;

        qDebug（）<    }

    /// 读入每个结点的后继succeed
    while（!inStream.atEnd（））
    {
        QString str = inStream.readLine（）;

        if（str == ““）  // 如果是空行，继续读取
            continue;

        QStringList slist = str.split（QRegularexpression（“\\s+“））;

        int Id1 = getID（slist[0]）;
        int Id2 = getID（slist[1]）;

        Succeed s1（Id2slist[2].toInt（））;
        Succeed s2（Id1slist[2].toInt（））;

        nodes[Id1].succeeds.push_back（s1）;
        nodes[Id2].succeeds.push_back（s2）;
    }

    return true;
}

void Graph::printGraph（）
{
    for（int i=0; i    {
        qDebug（）<
        for（int k=0; k        {
            qDebug（）<        }
    }
}

int Graph::getID（QString nodeName）
{
    for（int i=0; i    {
        if（nodes[i].nodeName == nodeName）
            return i;
    }
    return -1;
}

QString Graph::getName（int id）
{
    return nodes[id].nodeName;
}

void Graph::setNodeObstacle（QPoint p）
{
    for（int i=0; i < num;i++）
    {
        if（nodes[i].pos == p）
        {
            nodes[i].isObstacle = !nodes[i].isObstacle;
            break;
        }
    }
}

void Graph::getMat（）
{
    mat = new int[num*num];

    for（int i=0; i    {
        for（int k=0; k        {
            mat[i*num+k] =MAX_INT;
            if（i==k）
                mat[i*num+k]=0;
        }
  

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2017-02-17 21:54  Floyd算法求解最短行驶路径\
     文件         166  2017-02-17 21:54  Floyd算法求解最短行驶路径\readme.txt
     目录           0  2017-02-17 21:51  Floyd算法求解最短行驶路径\代码\
     文件        4759  2017-01-06 13:14  Floyd算法求解最短行驶路径\代码\graph.cpp
     文件        1417  2017-01-06 13:04  Floyd算法求解最短行驶路径\代码\graph.h
     目录           0  2017-02-17 17:12  Floyd算法求解最短行驶路径\演示程序\
     文件     4604928  2016-11-20 11:47  Floyd算法求解最短行驶路径\演示程序\Qt5Core.dll
     文件     4622336  2013-12-09 02:03  Floyd算法求解最短行驶路径\演示程序\Qt5Gui.dll
     文件     6281216  2013-12-09 02:08  Floyd算法求解最短行驶路径\演示程序\Qt5Widgets.dll
     文件      522752  2017-02-17 21:45  Floyd算法求解最短行驶路径\演示程序\ShortestPath.exe
     目录           0  2017-02-17 17:12  Floyd算法求解最短行驶路径\演示程序\accessible\
     文件       65536  2013-12-09 02:38  Floyd算法求解最短行驶路径\演示程序\accessible\qtaccessiblequick.dll
     文件     2197614  2013-12-09 02:38  Floyd算法求解最短行驶路径\演示程序\accessible\qtaccessiblequickd.dll
     文件      202240  2013-12-09 02:15  Floyd算法求解最短行驶路径\演示程序\accessible\qtaccessiblewidgets.dll
     文件     3825221  2013-12-09 02:15  Floyd算法求解最短行驶路径\演示程序\accessible\qtaccessiblewidgetsd.dll
     目录           0  2017-02-17 17:12  Floyd算法求解最短行驶路径\演示程序\iconengines\
     文件       60928  2013-12-09 02:16  Floyd算法求解最短行驶路径\演示程序\iconengines\qsvgicon.dll
     文件      828466  2013-12-09 02:16  Floyd算法求解最短行驶路径\演示程序\iconengines\qsvgicond.dll
     文件    22378434  2013-04-23 00:03  Floyd算法求解最短行驶路径\演示程序\icudt51.dll
     文件     3369922  2013-04-23 00:03  Floyd算法求解最短行驶路径\演示程序\icuin51.dll
     文件     1978690  2013-04-23 00:03  Floyd算法求解最短行驶路径\演示程序\icuuc51.dll
     目录           0  2017-02-17 17:12  Floyd算法求解最短行驶路径\演示程序\imageformats\
     文件       51200  2013-12-09 02:13  Floyd算法求解最短行驶路径\演示程序\imageformats\qgif.dll
     文件      658356  2013-12-09 02:13  Floyd算法求解最短行驶路径\演示程序\imageformats\qgifd.dll
     文件       52224  2013-12-09 02:13  Floyd算法求解最短行驶路径\演示程序\imageformats\qico.dll
     文件      667705  2013-12-09 02:13  Floyd算法求解最短行驶路径\演示程序\imageformats\qicod.dll
     文件      261120  2013-12-09 02:13  Floyd算法求解最短行驶路径\演示程序\imageformats\qjpeg.dll
     文件     1580168  2013-12-09 02:13  Floyd算法求解最短行驶路径\演示程序\imageformats\qjpegd.dll
     文件      381952  2013-12-09 02:23  Floyd算法求解最短行驶路径\演示程序\imageformats\qmng.dll
     文件     1383577  2013-12-09 02:23  Floyd算法求解最短行驶路径\演示程序\imageformats\qmngd.dll
     文件       46080  2013-12-09 02:16  Floyd算法求解最短行驶路径\演示程序\imageformats\qsvg.dll
............此处省略32个文件信息