图的综合应用-迪杰斯特拉算法(导游图)

数据结构的大实验  基本跟线性链表的什么学生管理系统没什么区别 还有什么查询景点之类的 对于这种的系统函数写完了 

但是主函数偷懒了没写 唯一有算法的就是迪杰斯特拉求两个景点的最短路径了 图是用邻接矩阵存的

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 100
#define oo 99999999
class Ciceroni
{
public:
    int num_xuhao;
    string num_bianhao;//景点编号
    string name;//景点名称
    string pro;//景点简介
};
class map
{
public:
    Ciceroni cic[MAX];//存景点的数组
    int AdjacencyMatrix[MAX][MAX];//景点邻接矩阵
    int sum;//景点的总数
    map();//初始化
    void InputNode();//输入点
    bool AddNode();//加点
    void BuildMap();//构建图
    int AddEdge();//加边 //0-退出 1-正确 2-无点
    void QueryNode();//查询点
    void Queryminpath();//查询两点最短路径 迪杰斯特拉
    void Oueryminpath_s();//查询多点最短路径
};
map::map()
{
    sum=0;
    for(int i=0; i<MAX; i++)
        for(int j=0; j<MAX; j++)
            AdjacencyMatrix[i][j]=oo;
}
void map::InputNode()
{
    cout<<"exit-0"<<endl;
    while(1)
        if(!AddNode())
            break;
    if(!sum)
        cout<<"input defeat"<<endl;
    else
        cout<<"input success"<<endl;
    cout<<endl;
}
bool map::AddNode()
{
    string num;
    cout<<"please input num of node"<<endl;
    cin>>num;
    if(num=="0")
        return 0;
    cic[++sum].num_bianhao=num;
    cout<<"please input name of node"<<endl;
    cin>>cic[sum].name;
    cout<<"please input pro of node"<<endl;
    cin>>cic[sum].pro;
    cic[sum].num_xuhao=sum;
    cout<<endl;
    return 1;
}
int map::AddEdge()
{
    string startnum,endnum;
    int dis,s=-1,e=-1;
    cout<<"input start node's num, end node's num, distance"<<endl;
    cin>>startnum>>endnum>>dis;
    if(startnum==endnum&&endnum=="0"&&!dis)
        return 0;
    for(int i=1; i<=sum; i++)
    {
        if(cic[i].num_bianhao==startnum)
            s=i;
        if(cic[i].num_bianhao==endnum)
            e=i;
        if(s!=-1&&e!=-1)
            break;
    }
    if(s==-1||e==-1)
        return 2;
    AdjacencyMatrix[s][e]=AdjacencyMatrix[e][s]=dis;
    return 1;
}
void map::BuildMap()
{
    cout<<"exit input 0_0_0"<<endl;
    while(1)
    {
        int s=AddEdge();
        if(!s) break;
        if(s==2) cout<<"input num error"<<endl;
        cout<<endl;
    }
    cout<<"bulid success"<<endl;
}
void map::QueryNode()
{
    cout<<"input node's num"<<endl;
    string num;
    cin>>num;
    int flag=0,i,j;
    for(i=1; i<=sum; i++)
        if(cic[i].num_bianhao==num)
        {
            flag=1;
            break;
        }
    if(flag)
    {
        cout<<"node's num:"<<endl<<cic[i].num_bianhao<<endl;
        cout<<"node's name:"<<endl<<cic[i].name<<endl;
        cout<<"node's pro:"<<endl<<cic[i].pro<<endl;
        cout<<"this node can arrive:"<<endl;
        for(j=1; j<=sum; j++)
            if(AdjacencyMatrix[i][j]<oo)
                cout<<"("<<cic[j].num_bianhao<<")"<<cic[j].name<<endl;
    }
    else
        cout<<"no this node"<<endl;
}
void map::Queryminpath()
{
    int distance[MAX];
    bool final[MAX];
    int pre[MAX][MAX];
    int s=-1,e=-1;
    string start,end;
    cout<<"input start num end num"<<endl;
    cin>>start>>end;
    for(int i=1; i<=sum; i++)
    {
        if(cic[i].num_bianhao==start)
            s=i;
        if(cic[i].num_bianhao==end)
            e=i;
        if(s!=-1&&e!=-1)
            break;
    }
    if(s==-1||e==-1)
    {
        cout<<"no node"<<endl;
        return;
    }
    memset(final,0,sizeof(final));
    memset(pre,0,sizeof(pre));
    for(int i=1; i<=sum; i++)
    {
        distance[i]=AdjacencyMatrix[s][i];
        if(distance[i]<oo)
            pre[i][1]=i;
    }
    distance[s]=0;
    final[s]=1;
    for(int i=2; i<=sum; i++)
    {
        int min=oo,p;
        for( int j=1; j<=sum; j++)
            if(!final[j]&&distance[j]<min)
                min=distance[j],p=j;
        final[p]=1;
        for(int j=1; j<=sum; j++)
            if(!final[j]&&(min+AdjacencyMatrix[p][j])<distance[j])
            {
                distance[j]=min+AdjacencyMatrix[p][j];
                for(int k=1; k<=sum; k++)
                    pre[j][k]=pre[p][k];
                for(int k=1; k<=sum; k++)
                    if(!pre[j][k])
                    {
                        pre[j][k]=j;
                        break;
                    }
            }
    }
    if(pre[e][1])
    {
        cout<<"the min distace between "<<cic[s].name<<" and "<<cic[e].name<<" is "<<distance[e]<<endl;
        cout<<"the path is :"<<endl;
        for(int k=1; k<=sum; k++)
        {
            if(!pre[e][k])
                break;
            cout<<cic[pre[e][k]].name<<" ";
        }
        cout<<endl;
    }
    else
        cout<<"no path between "<<cic[s].name<<" and "<<cic[e].name<<endl;
}

int main()
{
    map a;
    int n;
    do
    {
        system("cls");
        cout<<"********************************************************"<<endl;
        cout<<"*   welcome come to this xitong made by HanFangchong   *"<<endl;
        cout<<"*                                                      *"<<endl;
        cout<<"*      1-build node          2-build edge              *"<<endl;
        cout<<"*                                                      *"<<endl;
        cout<<"*      3-add node            4-add edge                *"<<endl;
        cout<<"*                                                      *"<<endl;
        cout<<"*      5-query node          6-query minpath           *"<<endl;
        cout<<"*                                                      *"<<endl;
        cout<<"*                    0-exit                            *"<<endl;
        cout<<"********************************************************"<<endl;
        printf("Selcet the operation you want:\n");
        cin>>n;
        switch(n)
        {
        case 1:
        {
            system("cls");
            a.InputNode();
            break;
        }
        case 2:
        {
            system("cls");
            a.BuildMap();
            break;
        }
        case 3:
        {
            system("cls");
            a.AddNode();
            break;
        }
        case 4:
        {
            system("cls");
            a.AddEdge();
            break;
        }
        case 5:
        {
            system("cls");
            a.QueryNode();
            int s;
            cout<<"exit-0"<<endl;
            cin>>s;
            if(!s)
                break;
        }
        case 6:
        {
            system("cls");
            a.Queryminpath();
            int s;
            cout<<"exit-0"<<endl;
            cin>>s;
            if(!s)
                break;
        }
        }
    }
    while(n);
    cout<<"thank for your using";
    return 0;
}