数据结构实训(大作业)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;
        }
        }
    }
}