数据结构实验课题：基于Dijsktra算法的最短路径求解

#include<bits/stdc++.h>
#define MAXINT 0x3f3f3f3f
#define Line cout<<"-----------------------------------------\n"
using namespace std;
typedef struct{
    int n,m;//城市数，路径数
    int **data;//邻接矩阵
    string *cityname;//存城市名
}Seq;
int y;
void menu()
{
    cout<<" **************************************\n\n";
    cout<<"  实验：基于Dijsktra算法的最短路求解：\n\n";
    cout<<"    1.邻接矩阵创建图\n";
    cout<<"    2.求两个指定点之间的最短路径\n";
    cout<<"    0.退出\n\n";
    cout<<" **************************************\n\n";
}
int LocateVex(Seq G,string c)///查找城市c在图中的位置
{
    for(int i=0;i<G.n;i++)
        if(c==G.cityname[i])
            return i;
    return -1;
}
bool CreatGraph(Seq &G)///邻接矩阵建图
{
    int dis,s,e;string start,end1;
    cout<<"请输入城市个数：";cin>>G.n;
    cout<<"请输入城市间路径条数：";cin>>G.m;
    if(!G.n)///城市数为0的情况
        return false;
    G.data=new int*[G.n];
    for(int i=0;i<G.n;i++)G.data[i]=new int[G.n];
    G.cityname=new string[G.n];
    cout<<"请输入每个城市的名称：";
    for(int i=0;i<G.n;i++)
        cin>>G.cityname[i];
    for(int i=0;i<G.n;i++)
        for(int j=0;j<G.n;j++)
            if(i==j)G.data[i][j]=0;
            else G.data[i][j]=MAXINT;
    cout<<"请输入每条路径的起始点、终点和距离：\n";
    for(int j=1;j<=G.m;j++){
        cin>>start>>end1>>dis;
        s=LocateVex(G,start),e=LocateVex(G,end1);
        if(s==-1||e==-1){
            cout<<"该条路径不符合标准，请重新输入！\n";
            j--;
            continue;
        }
        if(dis<0||dis>MAXINT){
            cout<<"该条路径的长度不符合标准，请重新输入！\n";
            j--;
            continue;
        }
        if(dis<G.data[s][e])///重边情况
            G.data[s][e]=dis;
    }
    return true;
}
void Dijkstra(Seq G)///Dijkstra算法
{
    string start,end1;
    cout<<"请输入待求最短路径的城市起点和终点：";
    cin>>start>>end1;
    int s,e,t=0;
    s=LocateVex(G,start),e=LocateVex(G,end1);
    if(s==-1||e==-1){
        cout<<"该输入不符合标准，请重新输入！\n";
        return;
    }
    if(s==e){///自环情况
        cout<<start<<"和"<<end1<<"之间最短路径长度为：0\n";
        cout<<"该路径为："<<start<<"\n";
        return;
    }
    int dis[G.n]={},book[G.n]={},path[G.n]={};///三个数组作用分别为记录最短路径长度，标记作用，记录前驱点
    for(int i=0;i<G.n;i++){
        dis[i]=G.data[s][i];
        if(dis[i]<MAXINT)
            path[i]=s;
        else path[i]=-1;
    }
    book[s]=1;
    for(int j=1;j<G.n;j++){
        int MINdis=MAXINT,k=-1;
        for(int i=0;i<G.n;i++){
            if(!book[i]&&dis[i]<MINdis){
                MINdis=dis[i];
                k=i;
            }
        }
        if(k==-1){
            cout<<start<<"和"<<end1<<"之间不存在路径！\n";
            return;
        }
        book[k]=1;
        if(k==e)break;
        for(int w=0;w<G.n;w++){
            if(!book[w]&&dis[k]+G.data[k][w]<dis[w]){
                dis[w]=dis[k]+G.data[k][w];
                path[w]=k;
            }
        }
    }
    if(dis[e]<MAXINT)
        cout<<start<<"和"<<end1<<"之间最短路径长度为："<<dis[e]<<endl;
    else{
        cout<<start<<"和"<<end1<<"之间不存在路径！\n";
        return;
    }
    /*输出路径*/
    cout<<"该路径为：";
    int node[G.n]={},q=1,y=1,i=e;
    while(y||q){
        if(y&&i!=s){
            node[q++]=i;
            i=path[i];
        }
        else{
            cout<<G.cityname[i]<<' ';
            i=node[--q];
            y=0;
        }
    }
    cout<<"\n";
}
/*
void OUT(Seq G)
{
    for(int i=0;i<G.n;i++){
        for(int j=0;j<G.n;j++){
            if(G.data[i][j]==MAXINT)
                cout<<"#"<<' ';
            else
                cout<<G.data[i][j]<<' ';
        }
        cout<<endl;
    }
}
*/
int main()
{
    menu();
    Seq Graph;
    int choose=-1;
    while(choose){
        cout<<"\n请输入指令：";
        cin>>choose;
        if(!y&&choose!=1&&choose!=0){
            cout<<endl;Line;
            cout<<"请先建图！\n";
            Line;continue;
        }
        cout<<endl;Line;
        switch(choose){
            case 0: cout<<"退出成功！\n";Line;break;
            case 1: system("cls");menu();Line;
                    if(CreatGraph(Graph))
                        cout<<"创建图成功！\n";
                    else
                        cout<<"创建图失败！\n";
                    Line;y=1;
                    break;
            case 2: Dijkstra(Graph);
                    Line;
                    break;
            default:cout<<"指令不存在，请重新输入！\n";
                    Line;
                    break;
        }
    }
    return 0;
}
/*
1 2 5
2 3 2
4 1 2
1 5 4
2 4 9
5 4 7
5 2 6
3 5 6
6 3 2
5 6 5
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189