xiaoxiaojinglinger 2020-02-07 17:45 采纳率: 0%
浏览 1892

Dijsktra算法结果出错:terminate called after throwing an instance of 'std::logic_error' what(): basic_string::_S_construct null not valid

结果:terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_S_construct null not valid

#include <iostream>
#include <sstream>
#include <string.h>
#include <vector>
#include<fstream>
#define MaxInt 32767                                        //表示极大值,即∞
#define MVNum 100                                           //最大顶点数
using namespace std;
typedef int ArcType;                                        //假设边的权值类型为整型

int *D=new int[MVNum];                                      //用于记录最短路的长度
bool *S=new bool[MVNum]();                                      //标记顶点是否进入S集合S={};
int *Path=new int[MVNum];                                   //用于记录最短路顶点的前驱

//------------图的顶点结构----------------- 
typedef struct{ 
    char name[100];
    char info[1000];
}VertexType; //顶点结构

//------------图的邻接矩阵-----------------
typedef struct{ 
    VertexType vexs[MVNum];                                 //顶点表 
    ArcType arcs[MVNum][MVNum];                             //邻接矩阵 
    int vexnum,arcnum;                                      //图的当前点数和边数 
}AMGraph;

int LocateVex(AMGraph G , string vname){
    //确定点v在G中的位置
    for(int i = 0; i < G.vexnum; ++i)
        if(G.vexs[i].name== vname)
            return i;
   return -1;
}//LocateVex

//定义字符串分割函数 
vector<string> split(const string& str, const string& delim) {  
    vector<string> res;  
    if("" == str) return res;  
    //先将要切割的字符串从string类型转换为char*类型  
    char * strs = new char[str.length() + 1] ; //不要忘了  
    strcpy(strs, str.c_str());   

    char * d = new char[delim.length() + 1];  
    strcpy(d, delim.c_str());  

    char *p = strtok(strs, d);  
    while(p) {  
        string s = p; //分割得到的字符串转换为string类型  
        res.push_back(s); //存入结果数组  
        p = strtok(NULL,d);  
    }  

    return res;  
}

void CreateUDN(AMGraph &G,char filename[]){ 
    //采用邻接矩阵表示法,创建无向网G 
    FILE *in;
    char *ch=new char[1000];
    char* s;
    vector<string> res;
    if((in=fopen(filename,"r"))==NULL){
        cout<<"无法打开graph文件!"<<endl;
        exit(0);
    }
    //读取总顶点数,总边数
     fgets(s,1000,in);
     res=split(s, " ");  
     stringstream ss,kk;
     ss<<res[0];
     ss>>G.vexnum;
     cout<<G.vexnum<<endl;
     kk<<res[1];
     kk>>G.arcnum;
     cout<<G.arcnum<<endl;
    //读取顶点信息 
    for(int i=0;i<G.vexnum;i++){
        fgets(s,1000,in);
        res=split(s, " "); 
        strcpy(G.vexs[i].name, res[0].c_str());
        strcpy(G.vexs[i].info, res[1].c_str());
    }
    //读取边的信息
    int m,n;
    for(int i=0;i<G.arcnum;i++){
        stringstream zz;
        fgets(s,1000,in);
        res=split(s, " ");  
        m = LocateVex(G, res[0]);  n = LocateVex(G, res[1]);        //确定两个顶点在G中的位置,即顶点数组的下标 
        zz<<res[2];
        zz>>G.arcs[m][n];                                   //设置边的权重 
        G.arcs[n][m] = G.arcs[m][n];    
        zz.str("");         
    }
    fclose(in);
}//CreateUDN

void ShortestPath_DIJ(AMGraph G, int v0){ 
    //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 
    int v , i , w , min;
    int n = G.vexnum;                                       //n为G中顶点的个数 

    for(v = 0; v < n; ++v){                                 //n个顶点依次初始化 
        S[v] = false;                                       //S初始为空集 
        D[v] = G.arcs[v0][v];                               //将v0到各个终点的最短路径长度初始化为弧上的权值 
        if(D[v] < MaxInt)  Path [v] = v0;                   //如果v0和v之间有弧,则将v的前驱置为v0 
        else Path [v] = -1;                                 //如果v0和v之间无弧,则将v的前驱置为-1 
    }//for 

    S[v0]=true;                                             //将v0加入S 
    D[v0]=0;                                                //源点到源点的距离为0 

    /*―初始化结束,开始主循环,每次求得v0到某个顶点v的最短路径,将v加到S集―*/ 
    for(i = 1;i < n; ++i){                                  //对其余n-1个顶点,依次进行计算 
        min= MaxInt; 
        for(w = 0; w < n; ++w) 
            if(!S[w] && D[w] < min){                        //选择一条当前的最短路径,终点为v 
                v = w; 
                min = D[w];
            }//if           
        S[v]=true;                                          //将v加入S 
        for(w = 0;w < n; ++w)                               //更新从v0出发到集合V?S上所有顶点的最短路径长度 
            if(!S[w] && (D[v] + G.arcs[v][w] < D[w])){ 
                D[w] = D[v] + G.arcs[v][w];                 //更新D[w] 
                Path [w] = v;                               //更改w的前驱为v 
            }//if 
    }//for  
}//ShortestPath_DIJ

void DisplayPath(AMGraph G, int begin,int temp ){
    //显示最短路
    //cout<<Path[temp]<<endl;
    if(Path[temp] != -1){
        DisplayPath(G, begin,Path[temp]);   
        cout<<G.vexs[Path[temp]].name<<"-->";   
    }

}//DisplayPath

int main()
{
    //cout << "************算法6.10 迪杰斯特拉算法**************" << endl << endl;
    AMGraph G; 
    int i , j ,fuwu,jd,start, destination;
    char f1[]={"graph.txt"};
    CreateUDN(G,f1);
    cout <<endl;
    cout << "*****无向网G创建完成!*****" << endl;

    for(i = 0 ; i < G.vexnum ; ++i){
        for(j = 0; j < G.vexnum; ++j){
            if(j != G.vexnum - 1){
                if(G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] << "\t";
                else
                    cout << "∞" << "\t";
            }
            else{
                if(G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] <<endl;
                else
                    cout << "∞" <<endl;
            }
        }
    }//for

    cout << "************欢迎来到**************" << endl << endl;
    cout << "         1.查询景点信息          "<<endl;
    cout << "         2.问路查询              "<<endl;
    cout << "         3.退出                  "<<endl;
    cout<<"*****************请选择需要的服务(1-3)****************"<<endl;
    cin>>fuwu;
    switch(fuwu){
        case 1:cout<<"本校景点有:"<<endl;
               for(i=0;i<G.vexnum;i++){
                  cout<<i<<":"<<G.vexs[i].name<<endl;
               }
               cout<<"请选择需要查询的景点"<<endl;
               cin>>jd;
               cout<<G.vexs[jd].info<<endl;
        case 2:cout<<"本校景点有:"<<endl;
               for(i=0;i<G.vexnum;i++){
                  cout<<i<<":"<<G.vexs[i].name<<endl;
               }
               cout<<"请输入您的所在地"<<endl;
               cin>>start;
               cout<<"请输入您的目的地"<<endl;
               cin>>destination;
               ShortestPath_DIJ(G,start);
               cout<<"路径是:";
               DisplayPath(G,start,destination);
               cout<<G.vexs[destination].name<<endl<<"最短距离是:"<<endl;
               cout<<D[destination]<<endl;
        case 3: exit(0);
    } 
    return 0;
}//main

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿
    • ¥100 关于使用MATLAB中copularnd函数的问题
    • ¥20 在虚拟机的pycharm上
    • ¥15 jupyterthemes 设置完毕后没有效果