当前位置:   article > 正文

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

基于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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/711053
推荐阅读
相关标签
  

闽ICP备14008679号