数据结构实训(大作业)c++模拟北斗卫星导航系统简单的迪杰斯特拉算法

简介: 数据结构实训(大作业)c++模拟北斗卫星导航系统简单的迪杰斯特拉算法

实现功能:

 

直接给出代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 100;
unordered_map<string, int> umap_ci; //城市_数字的映射
unordered_map<int, string> umap_ic; //数字_城市
int g[N][N];
int st[N], dist[N], pre[N], del[N];
int n = 19, idx = 20;
void init()
{
    memset(g, 0x3f, sizeof g);
    umap_ci["北京"] = 1;
    umap_ci["天津"] = 2;
    umap_ci["郑州"] = 3;
    umap_ci["徐州"] = 4;
    umap_ci["上海"] = 5;
    umap_ci["武汉"] = 6;
    umap_ci["南昌"] = 7;
    umap_ci["株洲"] = 8;
    umap_ci["福州"] = 9;
    umap_ci["广州"] = 10;
    umap_ci["深圳"] = 11;
    umap_ci["西宁"] = 12;
    umap_ci["柳州"] = 13;
    umap_ci["贵阳"] = 14;
    umap_ci["昆明"] = 15;
    umap_ci["成都"] = 16;
    umap_ci["西安"] = 17;
    umap_ci["兰州"] = 18;
    umap_ci["南宁"] = 19;
    umap_ic[1] = "北京";
    umap_ic[2] = "天津";
    umap_ic[3] = "郑州";
    umap_ic[4] = "徐州";
    umap_ic[5] = "上海";
    umap_ic[6] = "武汉";
    umap_ic[7] = "南昌";
    umap_ic[8] = "株洲";
    umap_ic[9] = "福州";
    umap_ic[10] = "广州";
    umap_ic[11] = "深圳";
    umap_ic[12] = "西宁";
    umap_ic[13] = "柳州";
    umap_ic[14] = "贵阳";
    umap_ic[15] = "昆明";
    umap_ic[16] = "成都";
    umap_ic[17] = "西安";
    umap_ic[18] = "兰州";
    umap_ic[19] = "南宁";
    //建立无向边
    g[1][2] = g[2][1] = 137;
    g[1][3] = g[3][1] = 695;
    g[2][4] = g[4][2] = 674;
    g[3][4] = g[4][3] = 349;
    g[3][6] = g[6][3] = 534;
    g[3][17] = g[17][3] = 511;
    g[4][5] = g[5][4] = 651;
    g[5][7] = g[7][5] = 825;
    g[6][8] = g[8][6] = 409;
    g[7][8] = g[8][7] = 367;
    g[7][9] = g[9][7] = 622;
    g[8][10] = g[10][8] = 675;
    g[8][13] = g[13][8] = 672;
    g[8][14] = g[14][8] = 902;
    g[10][11] = g[11][10] = 140;
    g[19][13] = g[13][19] = 255;
    g[13][14] = g[14][13] = 607;
    g[14][16] = g[16][14] = 967;
    g[14][15] = g[15][14] = 639;
    g[15][16] = g[16][15] = 1100;
    g[16][17] = g[17][16] = 842;
    g[17][18] = g[18][17] = 676;
    g[18][12] = g[12][18] = 216;
}
int dijkstra(int startId, int endId)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(pre, 0, sizeof pre);
    dist[startId] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && !del[j] && (dist[t] > dist[j] || t == -1))
                t = j;
        }
        st[t] = 1;
        if (t == endId) break;
        for (int k = 1; k <= n; k++)
        {
            if (dist[k] > dist[t] + g[t][k])
            {
                dist[k] = dist[t] + g[t][k];
                pre[k] = t;
            }
        }
    }
    if (dist[endId] == 0x3f3f3f3f)  return -1;
    else return dist[endId];
}
bool add(string a)
{
    if (idx > 100)  return 0;
    umap_ci[a] = idx; umap_ic[idx] = a;
    string city; int w;
    cout << "请输入相连的城市及其距离: " << endl;
    while (cin >> city >> w)
    {
        if (city == "0" && w == 0)   break; //输入错误数据会结束
        int id = umap_ci[city];
        g[id][idx] = g[idx][id] = w;
    }
    idx++; n++;
    return 1;
}
bool delCity(string a)
{
    if (umap_ci.find(a) == umap_ci.end())   return 0;
    int id = umap_ci[a];
    del[id] = 1;
    for (int i = 1; i <= n; i++)
        g[id][i] = g[i][id] = 0x3f3f3f3f;
    return 1;
}
void findAdjacencyPoint(string city)
{
    int id = umap_ci[city];
    cout << "临界点:";
    for (int i = 1; i <= n; i++)
    {
        if (g[id][i] < 0x3f3f3f3f)
            cout << umap_ic[i] << " ";
    }
    cout << endl;
}
bool modify(string start, string end, int w)
{
    int startId = umap_ci[start];
    int endId = umap_ci[end];
    if (del[startId] || del[endId] || umap_ci.find(start) == umap_ci.end() || umap_ci.find(end) == umap_ci.end())
    {
        cout << "起点或者终点城市没有添加过或者已经被删除" << endl;
        return false;
    }
    if (w <= 0 || w >= 0x3f3f3f3f)
    {
        cout << "输入的距离不是一个合理的值!!!" << endl;
        return false;
    }
    g[startId][endId] = g[endId][startId] = w;
    return true;
}
void findShortestPath()
{
    string start, end;
    vector<string> v;  //存储路径的向量
    cout << "请输入起始地和目标地点: " << endl;
    cin >> start >> end;
    int startId = umap_ci[start];
    int endId = umap_ci[end];
    if (del[startId] || del[endId] || umap_ci.find(start) == umap_ci.end() || umap_ci.find(end) == umap_ci.end())
    {
        cout << "起点或者终点城市没有添加过或者已经被删除" << endl;
        return;
    }
    int t = dijkstra(startId, endId);
    if (t == -1)
    {
        cout << "城市" << " " << start << " " << "到不了城市 " << end << " " << endl;
        return;
    }
    while (endId)
    {
        v.push_back(umap_ic[endId]);
        if (endId == startId)  break;
        endId = pre[endId];
    }
    cout << "经过的最短路径为: " << endl;
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i] << "->";
    cout << t << endl;
}
void mune()
{
    cout << "----------------------------------------------------" << endl;
    cout << "1.    添加城市" << endl;
    cout << "2.    删除城市" << endl;
    cout << "3.    查询最短路径" << endl;
    cout << "4.    查询相邻城市" << endl;
    cout << "5.    修改两个城市之间的距离" << endl;
}
int main()
{
    init();
    mune();
    int op = -1;
    while (true)
    {
        cout << "请选择要进行的操作(输入为0结束程序): " << endl;
        cin >> op;
        if (op == 0)    return 0;
        switch (op)
        {
        case 1:
        {
            cout << "请输入你要添加的城市名字: " << endl;
            string a; cin >> a;
            if (add(a))
                cout << "添加" << a << "城市成功" << endl;
            else
                cout << "城市已到达上限" << endl;
            break;
        }
        case 2:
        {
            cout << "请输入你要删除的城市: " << endl;
            string a; cin >> a;
            if (delCity(a))
                cout << "删除城市" << a << "成功" << endl;
            else
                cout << "删除城市失败,请检查输入的城市是否错在" << endl;
            break;
        }
        case 3:
        {
            findShortestPath();
            break;
        }
        case 4:
        {
            cout << "请输入城市: " << endl;
            string a; cin >> a;
            findAdjacencyPoint(a);
            break;
        }
        case 5:
        {
            cout << "请输入你要修改的城市名字,及其要修改的距离" << endl;
            string a, b; int w;
            cin >> a >> b >> w;
            modify(a, b, w);
            break;
        }
        }
    }
}
目录
相关文章
|
2月前
|
机器学习/深度学习 算法 TensorFlow
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
动物识别系统。本项目以Python作为主要编程语言,并基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集4种常见的动物图像数据集(猫、狗、鸡、马)然后进行模型训练,得到一个识别精度较高的模型文件,然后保存为本地格式的H5格式文件。再基于Django开发Web网页端操作界面,实现用户上传一张动物图片,识别其名称。
84 1
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
|
2月前
|
机器学习/深度学习 人工智能 算法
植物病害识别系统Python+卷积神经网络算法+图像识别+人工智能项目+深度学习项目+计算机课设项目+Django网页界面
植物病害识别系统。本系统使用Python作为主要编程语言,通过收集水稻常见的四种叶片病害图片('细菌性叶枯病', '稻瘟病', '褐斑病', '稻瘟条纹病毒病')作为后面模型训练用到的数据集。然后使用TensorFlow搭建卷积神经网络算法模型,并进行多轮迭代训练,最后得到一个识别精度较高的算法模型,然后将其保存为h5格式的本地模型文件。再使用Django搭建Web网页平台操作界面,实现用户上传一张测试图片识别其名称。
109 22
植物病害识别系统Python+卷积神经网络算法+图像识别+人工智能项目+深度学习项目+计算机课设项目+Django网页界面
|
16天前
|
监控 算法 数据安全/隐私保护
基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
本项目展示了基于FPGA与MATLAB实现的三帧差算法运动目标检测。使用Vivado 2019.2和MATLAB 2022a开发环境,通过对比连续三帧图像的像素值变化,有效识别运动区域。项目包括完整无水印的运行效果预览、详细中文注释的代码及操作步骤视频,适合学习和研究。
|
2月前
|
机器学习/深度学习 人工智能 算法
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
鸟类识别系统。本系统采用Python作为主要开发语言,通过使用加利福利亚大学开源的200种鸟类图像作为数据集。使用TensorFlow搭建ResNet50卷积神经网络算法模型,然后进行模型的迭代训练,得到一个识别精度较高的模型,然后在保存为本地的H5格式文件。在使用Django开发Web网页端操作界面,实现用户上传一张鸟类图像,识别其名称。
100 12
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
|
2月前
|
机器学习/深度学习 算法 TensorFlow
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高的模型文件,然后保存为本地的h5格式文件。再使用Django开发Web网页端操作界面,实现用户上传一张交通标志图片,识别其名称。
88 6
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
|
2月前
|
机器学习/深度学习 人工智能 算法
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
文本分类识别系统。本系统使用Python作为主要开发语言,首先收集了10种中文文本数据集("体育类", "财经类", "房产类", "家居类", "教育类", "科技类", "时尚类", "时政类", "游戏类", "娱乐类"),然后基于TensorFlow搭建CNN卷积神经网络算法模型。通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型,并保存为本地的h5格式。然后使用Django开发Web网页端操作界面,实现用户上传一段文本识别其所属的类别。
82 1
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
28天前
|
算法
基于最小二乘递推算法的系统参数辨识matlab仿真
该程序基于最小二乘递推(RLS)算法实现系统参数辨识,对参数a1、b1、a2、b2进行估计并计算误差及收敛曲线,对比不同信噪比下的估计误差。在MATLAB 2022a环境下运行,结果显示了四组误差曲线。RLS算法适用于实时、连续数据流中的动态参数辨识,通过递推方式快速调整参数估计,保持较低计算复杂度。
|
29天前
|
机器学习/深度学习 人工智能 开发框架
【AI系统】AI 学习方法与算法现状
在人工智能的历史长河中,我们见证了从规则驱动系统到现代机器学习模型的转变。AI的学习方法基于深度神经网络,通过前向传播、反向传播和梯度更新不断优化权重,实现从训练到推理的过程。当前,AI算法如CNN、RNN、GNN和GAN等在各自领域取得突破,推动技术进步的同时也带来了更大的挑战,要求算法工程师与系统设计师紧密合作,共同拓展AI技术的边界。
65 1
|
2月前
|
前端开发 搜索推荐 算法
中草药管理与推荐系统Python+Django网页界面+推荐算法+计算机课设系统+网站开发
中草药管理与推荐系统。本系统使用Python作为主要开发语言,前端使用HTML,CSS,BootStrap等技术和框架搭建前端界面,后端使用Django框架处理应用请求,使用Ajax等技术实现前后端的数据通信。实现了一个综合性的中草药管理与推荐平台。具体功能如下: - 系统分为普通用户和管理员两个角色 - 普通用户可以登录,注册、查看物品信息、收藏物品、发布评论、编辑个人信息、柱状图饼状图可视化物品信息、并依据用户注册时选择的标签进行推荐 和 根据用户对物品的评分 使用协同过滤推荐算法进行推荐 - 管理员可以在后台对用户和物品信息进行管理编辑
74 12
中草药管理与推荐系统Python+Django网页界面+推荐算法+计算机课设系统+网站开发
|
21天前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
27 0