数据结构 最短路径课设(源码+实验报告+视频讲解)(不要钱、用了自取)
创始人
2024-05-16 02:02:42
0

XI`AN TECHNOLOGICAL UNIVERSITY

课程设计报告

实验课程名称   算法与数据结构   

专    业:         

班    级:              

姓    名:               

学    号:         

实验学时:                        

指导教师:                     

成    绩:                        

        

    2023      1  7  日

目录

一、实验报告

        一、绪论

        二、基本要求

        三、信息描述

        五、详细设计

        六、调试与测试:

        八、总结

 源码:

视频上传比较麻烦,需要的同学可以联系我


一、实验报告

一、绪论

迪杰特斯拉算法思想:

设G=(V,E)是一个带权有向图,把顶点集合V分成两组,求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径,就将加入到集合S中。直到全部顶点都加入到S中,算法就结束了)。第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点V到S中各顶点的最短路径长度大于从源点V到V中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从V到此顶点的最短路径长度,V中的顶点的距离是从V到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

二、基本要求

(1)设计最短路径,包含以下方面:

1、用邻接矩阵存储一张带权有向图。

2、对图进行从某一源点到其他各顶点的最短路径

3、输出最后结果(路径名称、路径长度)。

三、信息描述

邻接矩阵建立包括:用二维数组存储信息。没有直达路径的为无穷。

用循环来判断最小值。

最终结果用一维数组存储。D[]存放源点到其他顶点的最短路径的长度,P[]存放该顶点最短路径的前驱顶点下标,visit[]为访问标识。初始全部值设为F,先把源点的标识设为T,后面每找到一个源点到其余顶点的最短路径,就将该顶点下标对应的标识置为T。直到全部顶点执行完毕。

输出一维数组D[]和P[],显示最终结果。

  • 总体设计

五、详细设计

  • 第一部分,进行对邻接矩阵的初始化,首先自己到自己的距离肯定为0,然后到其余结点初始化为MAX,然后通过一个for循环,对边进行数据存入,打印函数用来验证。

  • 第二部分对于结点类的创建(构造、拷贝构造、赋值运算符重载、比较方式的重载)类中存放每一个结点的下标、最短路径长度、前驱结点。

  •  第三部分:打印结果函数

  •  迪杰斯特拉算法部分(核心)

完成好邻接矩阵的初始化工作以后,输入我们的起点坐标,对于起点来说,从起点到达起点的距离肯定是0,然后将起点坐标置入优先队列中,进入循环,循环退出条件是优先队列为空

每次取堆顶元素,使用cur进行保存,之后就将此结点pop

利用cur找出所有可以从cur出发到达的所有结点,将这些结点保存到集合S中,对于集合中的所有结点进行:

newlength = node[Index]._length + Graph[Index][back];

// 如果新距离小于cur之前的最小距离,就将cur重新赋值,并入队列

   if (newlength < node[back]._length)

   {

    node[back]._length = newlength;

    node[back]._prev = Index;

    q.push(node[back]);

   }

六、调试与测试:

在我写代码的时候大部分问题都可以查资料解决,如何使用vector,如果使用优先级队列,以及思路的来源也是借助于网上的资料查看,视频讲解,耗费时间最多的应该就是对于自定义类型优先级队列第三个参数比较方式的确定,本来我的代码是这样通过结构体与函数指针来实现,不过也出现了类型不匹配的问题,最后通过使用类中对比较关系的重载写出了bool类型关于>符号的重载(因为要建大堆)。

七、程序清单和执行结果:清单中应有足够的注释

运行结果:

源码:

//(1)设计最短路径,包含以下方面:

//1、用邻接矩阵存储一张带权有向图。

//2、对图进行从某一源点到其他各顶点的最短路径

//了、输出最后结果(路径名称、路径长度)。

//三、信息描述

//邻接矩阵建立包括 : 用二维数组存储信息。没有直达路径的为无

//穷

//用循环来判断最小值

//最终结果用一维数组存储。D[]存放源点到其他顶点的最短路径的

//长度,P[]存放该顶点最短路径的前驱顶点下标

// 0 1 2   0 4 10  1 2 3  1 4 7  2 0 4  2 3 4  3 4 5  4 2 3

#include

#include

#include

using namespace std;

#include

#include

#define MAX 1000 // 不可到达

int V, E, S; // 顶点数、边数、起点

vector> Graph;

void CreatMyGraph() // 初始化邻接矩阵

{

    cout << "请输入顶点数、边数" << endl;

    cin >> V >> E;

    Graph.resize(V);

    for (int i = 0; i < V; i++)

    {

        Graph[i].resize(V);

        for (int j = 0; j < V; j++)

        {

            if (i == j)

                Graph[i][j] = 0; // 自己到自己赋值为0

            else

                Graph[i][j] = MAX;   // 默认初始化到其余顶点均为MAX

        }

    }

    /*Graph[0][1] = 2;

    Graph[0][3] = 1;

    Graph[1][3] = 3;

    Graph[1][4] = 7;

    Graph[2][0] = 4;

    Graph[3][2] = 2;

    Graph[3][4] = 2;

    Graph[3][5] = 8;

    Graph[3][6] = 4;

    Graph[4][6] = 1;

    Graph[6][5] = 1;

    Graph[2][5] = 5;*/

    int begin, end;

    int length;

    for (int i = 0; i < E; i++)

    {

        cout << "请输入第" << i + 1 << "条边的起点、终点、权值:" << endl;

        cin >> begin >> end >> length;

        Graph[begin][end] = length;   // 初始化邻接矩阵

    }

}

void PrintMyGraph()

{

    cout << "图的邻接矩阵存储为:" << endl;

    for (int i = 0; i < V; i++)

    {

        for (int j = 0; j < V; j++)

        {

            cout << Graph[i][j] << " ";

        }

        cout << endl;

    }

}

//typedef struct DjNode

//{

//  int _index;

//  int _length;

//  int _prev;

//}Node;

//Node BuyNode(int index, int length)

//{

//  Node* newnode = (Node*)malloc(sizeof(Node));

//  newnode->_index = index;

//  newnode->_length = length;

//  newnode->_prev = 0;

//  return newnode;

//}

//typedef bool (*PCOM)(const Node& left, const Node& right);

//bool Compare(const Node left, const Node right)

//{

//  return left._length > right._length;

//}

class Node

{

public:

    Node(int index, int length, int prev)

        : _index(index)

        , _length(length)

        , _prev(prev)

    {}

    Node(const Node& d)

    {

        _index = d._index;

        _length = d._length;

        _prev = d._prev;

    }

    Node& operator=(const Node& node)

    {

        if (this != &node)

        {

            _index = node._index;

            _length = node._length;

            _prev = node._prev;

        }

        return *this;

    }

    bool operator>(const Node& d)const

    {

        return _length > d._length;

    }

    bool operator<(const Node& d)const

    {

        return _length < d._length;

    }

    int _index;

    int _length;

    int _prev;

};

class Com

{

public:

    bool operator()(const Node&left, const Node&right)const

    {

        return left._length > right._length;

    }

};

void Print_output(int start, vector node)

{

    cout << "由" << start << "到其余各顶点距离分别为" << endl;

    for (int i = 0; i < V; i++)

    {

        if (i == start)

            continue;

        else

            cout << start << "->" << i << ": " << node[i]._length << endl;

    }

}

void Dijkstra_Algorithm()

{

    // 1、初始化输出数组D、P

    //vector D(V, MAX);  // 初始化最短长度数组D

    //vector P(V, 0); // 初始化前驱结点数组P

    vector node(V, Node(0,0,0));

    for (int i = 0; i < V; i++)

    {

        //node[i] = BuyNode(i, MAX); // 结点初始化

        node[i]._index = i;

        node[i]._length = MAX;

        node[i]._prev = 0;

    }

    // 2、初始化顶点D[S]

    cout << "请输入起点" << endl;

    cin >> S;

    node[S]._length = 0;

    // 3、创建优先队列,起点元素入队列

    priority_queue, greater> q;

    q.push(node[S]);

    while (!q.empty())

    {

        Node cur = q.top();

        q.pop(); // 取出堆顶元素并进行保存

        vector pre_next;

        int Index = cur._index;

        for (int i = 0; i < V; i++) // 将所有可以一步到达当前结点的元素下标全部保存到pre_next中

        {

            if (Graph[Index][i] > 0 && Graph[Index][i] != MAX)

                pre_next.push_back(i);

        }

        while (!pre_next.empty()) // 对于每一个可以到达cur的结点

        {

            int back = pre_next.back();   //访问一个取出一个

            pre_next.pop_back();

            // 新距离就为 从源点到back距离  加上  back到cur的距离

            int newlength = node[Index]._length + Graph[Index][back];

            // 如果新距离小于cur之前的最小距离,就将cur重新赋值,并入队列

            if (newlength < node[back]._length)

            {

                node[back]._length = newlength;

                node[back]._prev = Index;

                q.push(node[back]);

            }

        }

    }

    cout << endl;

    Print_output(S, node);

}

void _Dijkstra_Algorithm()

{

    cout << "Dijkstra_Algorithm :" << endl;

    int choice;

    while (1)

    {

        cout << "请输入:" << "[1]开始" << "[0]结束" << endl;

        cin >> choice;

        switch (choice)

        {

        case 1:

            Dijkstra_Algorithm();

            break;

        case 0:

            exit(0);

            break;

        }

    }

}

int main()

{

    int choice;

    while (1)

    {

        cout << "*******************************************" << endl;

        cout << "***************请输入请求:****************" << endl;

        cout << "***************[1]初始化数据***************" << endl;

        cout << "***************[2]迪杰斯特拉算法***********" << endl;

        cout << "***************[0]退出*********************" << endl;

        cout << "*******************************************" << endl;

        cin >> choice;

        switch (choice)

        {

        case 1:

            CreatMyGraph();

            break;

        case 2:

            _Dijkstra_Algorithm();

            break;

        case 0:

            exit(0);

            break;

        default:

            cout << "输入错误,请重新输入" << endl;

            break;

        }

    }

    return 0;

}

八、总结

通过这次课设,进一步提高了对于数据结构的认知,提升了自己的编程能力,了解了迪杰斯特拉算法在使用优先级队列来解决问题的便利之处。

 源码:

//(1)设计最短路径,包含以下方面:
//1、用邻接矩阵存储一张带权有向图。
//2、对图进行从某一源点到其他各顶点的最短路径
//了、输出最后结果(路径名称、路径长度)。
//三、信息描述
//邻接矩阵建立包括 : 用二维数组存储信息。没有直达路径的为无
//穷
//用循环来判断最小值
//最终结果用一维数组存储。D[]存放源点到其他顶点的最短路径的
//长度,P[]存放该顶点最短路径的前驱顶点下标
// 0 1 2   0 4 10  1 2 3  1 4 7  2 0 4  2 3 4  3 4 5  4 2 3
#include
#include
#include
using namespace std;
#include
#include
#define MAX 1000 // 不可到达
int V, E, S; // 顶点数、边数、起点vector> Graph;void CreatMyGraph() // 初始化邻接矩阵
{cout << "请输入顶点数、边数" << endl;cin >> V >> E;Graph.resize(V);for (int i = 0; i < V; i++){Graph[i].resize(V);for (int j = 0; j < V; j++){if (i == j)Graph[i][j] = 0;	// 自己到自己赋值为0elseGraph[i][j] = MAX;	// 默认初始化到其余顶点均为MAX}}/*Graph[0][1] = 2;Graph[0][3] = 1;Graph[1][3] = 3;Graph[1][4] = 7;Graph[2][0] = 4;Graph[3][2] = 2;Graph[3][4] = 2;Graph[3][5] = 8;Graph[3][6] = 4;Graph[4][6] = 1;Graph[6][5] = 1;Graph[2][5] = 5;*/int begin, end;int	length;for (int i = 0; i < E; i++){cout << "请输入第" << i + 1 << "条边的起点、终点、权值:" << endl;cin >> begin >> end >> length;Graph[begin][end] = length;	// 初始化邻接矩阵}
}void PrintMyGraph()
{cout << "图的邻接矩阵存储为:" << endl;for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){cout << Graph[i][j] << " ";}cout << endl;}
}//typedef struct DjNode
//{
//	int _index;
//	int _length;
//	int _prev;
//}Node;//Node BuyNode(int index, int length)
//{
//	Node* newnode = (Node*)malloc(sizeof(Node));
//	newnode->_index = index;
//	newnode->_length = length;
//	newnode->_prev = 0;
//	return newnode;
//}//typedef bool (*PCOM)(const Node& left, const Node& right);
//bool Compare(const Node left, const Node right)
//{
//	return left._length > right._length;
//}class Node
{
public:Node(int index, int length, int prev): _index(index), _length(length), _prev(prev){}Node(const Node& d){_index = d._index;_length = d._length;_prev = d._prev;}Node& operator=(const Node& node){if (this != &node){_index = node._index;_length = node._length;_prev = node._prev;}return *this;}bool operator>(const Node& d)const{return _length > d._length;}bool operator<(const Node& d)const{return _length < d._length;}int _index;int _length;int _prev;
};class Com
{
public:bool operator()(const Node&left, const Node&right)const{return left._length > right._length;}
};void Print_output(int start, vector node)
{cout << "由" << start << "到其余各顶点距离分别为" << endl;for (int i = 0; i < V; i++){if (i == start)continue;elsecout << start << "->" << i << ": " << node[i]._length << endl;}
}void Dijkstra_Algorithm()
{// 1、初始化输出数组D、P//vector D(V, MAX);	// 初始化最短长度数组D//vector P(V, 0);	// 初始化前驱结点数组Pvector node(V, Node(0,0,0));for (int i = 0; i < V; i++){//node[i] = BuyNode(i, MAX); // 结点初始化node[i]._index = i;node[i]._length = MAX;node[i]._prev = 0;}// 2、初始化顶点D[S]cout << "请输入起点" << endl;cin >> S;node[S]._length = 0;// 3、创建优先队列,起点元素入队列priority_queue, greater> q; q.push(node[S]);while (!q.empty()){Node cur = q.top();q.pop(); // 取出堆顶元素并进行保存vector pre_next;int Index = cur._index;for (int i = 0; i < V; i++) // 将所有可以一步到达当前结点的元素下标全部保存到pre_next中{if (Graph[Index][i] > 0 && Graph[Index][i] != MAX)pre_next.push_back(i);}while (!pre_next.empty())	// 对于每一个可以到达cur的结点{int back = pre_next.back();	//访问一个取出一个pre_next.pop_back();// 新距离就为 从源点到back距离  加上  back到cur的距离int newlength = node[Index]._length + Graph[Index][back];// 如果新距离小于cur之前的最小距离,就将cur重新赋值,并入队列if (newlength < node[back]._length){node[back]._length = newlength;node[back]._prev = Index;q.push(node[back]);}}}cout << endl;Print_output(S, node);
}void _Dijkstra_Algorithm()
{cout << "Dijkstra_Algorithm :" << endl;int choice;while (1){cout << "请输入:" << "[1]开始" << "[0]结束" << endl;cin >> choice;switch (choice){case 1:Dijkstra_Algorithm();break;case 0:exit(0);break;}}
}int main()
{int choice;while (1){cout << "*******************************************" << endl;cout << "***************请输入请求:****************" << endl;cout << "***************[1]初始化数据***************" << endl;cout << "***************[2]迪杰斯特拉算法***********" << endl;cout << "***************[0]退出*********************" << endl;cout << "*******************************************" << endl;cin >> choice;switch (choice){case 1:CreatMyGraph();break;case 2:_Dijkstra_Algorithm();break;case 0:exit(0);break;default:cout << "输入错误,请重新输入" << endl;break;}}return 0;
}

相关内容

热门资讯

鸿蒙怎样还原安卓系统,系统切换... 你有没有想过,鸿蒙系统竟然能还原安卓系统?这听起来是不是有点像魔法一样神奇?没错,今天就要带你一探究...
电脑安卓转苹果系统,系统迁移攻... 你有没有想过,有一天你的安卓手机突然变成了苹果的忠实粉丝,想要跳槽到iOS的阵营呢?这可不是什么天方...
安卓xp系统下载地址,轻松获取... 你有没有想过,手机系统也能穿越时空?没错,今天我要给你揭秘的就是这样一个神奇的存在——安卓XP系统。...
安卓系统怎么清理相册,安卓系统... 手机里的相册是不是越来越臃肿了?每次打开都感觉像是在翻山越岭,找一张照片都要费老鼻子劲。别急,今天就...
安卓系统安装ios转移,轻松实... 你有没有想过,手机系统之间的转换竟然也能如此神奇?没错,今天就要来聊聊安卓系统安装iOS转移这个话题...
安卓系统与ios系统的优势,系... 你有没有想过,为什么你的手机里装的是安卓系统而不是苹果的iOS系统呢?或者反过来,为什么你的朋友用的...
安卓系统游戏如何升级,轻松实现... 亲爱的安卓玩家们,你是否也和我一样,对安卓系统游戏升级这件事充满了好奇和期待呢?每次游戏更新,都仿佛...
安卓系统蛋仔派对,安卓系统下的... 你有没有发现,最近你的手机里多了一个超级好玩的游戏?没错,就是安卓系统上的“蛋仔派对”!这款游戏可是...
坚果3安卓原生系统,深度体验原... 你有没有听说过坚果3这款手机?它可是最近在数码圈里火得一塌糊涂呢!今天,我就要来给你详细介绍一下这款...
安卓子系统点不开,排查与解决指... 最近是不是你也遇到了安卓子系统点不开的烦恼?这可真是让人头疼啊!别急,今天就来给你详细解析一下这个问...
安卓系统经常误删文件,如何有效... 你有没有遇到过这种情况?手机里的文件突然不见了,找来找去,怎么也找不到。别急,这可能是安卓系统的小调...
安卓51系统如何破解,轻松解锁... 安卓51系统如何破解——探索未知的技术边界在数字化时代,手机已经成为我们生活中不可或缺的一部分。而安...
安卓系统怎么换回主题,安卓系统... 亲爱的手机控们,你是不是也和我一样,对安卓系统的主题换换换乐此不疲呢?不过,有时候换着换着,突然发现...
黑莓安卓系统 太垃圾,令人失望... 你有没有用过黑莓的安卓系统?别告诉我你没有,因为现在这个系统真的是太垃圾了!是的,你没听错,就是那个...
修改安卓系统权限代码,安卓系统... 你有没有想过,你的安卓手机里那些神秘的系统权限代码?它们就像隐藏在手机里的秘密通道,有时候让你觉得既...
虚拟大师安卓系统教程,教程详解... 你有没有想过,手机里的世界可以变得更加神奇?今天,就让我带你一起探索虚拟大师安卓系统的奥秘吧!想象你...
基于安卓系统个人博客,轻松构建... 你有没有想过,在这个信息爆炸的时代,拥有一片属于自己的网络小天地是多么酷的事情啊!想象每天都能在这里...
安卓怎么传到苹果系统,从安卓到... 你是不是也有过这样的烦恼:手机里存了好多好用的安卓应用,可是一换到苹果系统,就发现这些宝贝们都不见了...
安卓改系统字体app,安卓系统... 你有没有想过,手机上的字体也能变得个性十足?没错,就是那个安卓改系统字体app,它可是让手机界面焕然...
安卓系统重启密码错误,破解与预... 手机突然重启了,屏幕上竟然出现了密码输入的界面!这可怎么办?别急,让我来帮你一步步解决这个安卓系统重...