# 最短路径问题（无负边值）——Dijkstra 算法 Dijkstra算法使用了广度优先搜索解决了赋权有向图或无向图的单源最短路径问题。算法采用了贪心策略，分阶段的求解这个问题，这篇文章，我们进行详细的介绍。 #### 实现步骤 Dijkstra算法按阶段进行，在每个阶段，Dijkstra算法选择一个顶点 v ，它在所有未知顶点中具有最小的dv，同时算法声明从 s 到 v 的最短路径是已知的。阶段的其余部分由dw值的更新工作组成。 #### 代码实现

typedef string vertex;struct Node{    vertex data;    int weight = 0;    Node *next = NULL;    Node(vertex data,int weight, Node *next = NULL)    {        this->data = data;        this->weight = weight;        this->next = next;    }};

/*表  不考虑负边*/const int INFINITE = -1;  //距离 定义无限大struct Box{    bool known = false;    int dv = INFINITE;    vertex path;};

map<vertex, Box*> Dijkstra(vertex v,map<vertex, Node*> graph){    map<vertex, Box*> boxs = initBox(v, graph);    while (1)    {        map<vertex, Box*>::iterator it = boxs.begin();        int min = 99999999;        //key为当前阶段应当标记为已知的顶点        vertex key;        int flag = 0;        while (it != boxs.end())        {            if (it->second->known==false&& it->second->dv!= INFINITE &&it->second->dv < min)            {                min = it->second->dv;    //记录最短路径                key = it->first;        //记录最小路径的key                flag = 1;                //将flag置为1，说明，还有known为false的            }            it++;        }        //所有known都是true ，算法结束        if (flag == 0)        {            return boxs;        }        boxs[key]->known = true;        //将最小的顶点known置为true        //将所有与此顶点相邻接的点进行更新        Node* n = graph[key];        while (n != NULL)        {            //如果此顶点是已知的，就不虚要再处理了            if (boxs[n->data]->known == true)            {                n = n->next;                continue;            }            //此顶点计算出来到it2的路径            int d_new = boxs[key]->dv + n->weight;            //原本it2的路径长度            int d_old = boxs[n->data]->dv;            //需要更新            if (d_old == INFINITE || d_new < d_old)            {                boxs[n->data]->dv = d_new;                boxs[n->data]->path = key;            }            n = n->next;        }    }}

string printp(vertex p, map<vertex, Box*> boxs){    if (boxs[p]->dv == 0)    {        return p+"";    }    return printp(boxs[p]->path, boxs) + "->" + p;}//输出算法的结果map<vertex, string> printfDijkstra(map<vertex, Box*> boxs){    //用来存放输出的内容    map<vertex, string> outs;    vertex aim;    //找到起点    map<vertex, Box*>::iterator it = boxs.begin();    while (it != boxs.end())    {        if (boxs[it->first]->dv == 0) {            aim = it->first;            break;        }        it++;    }    it = boxs.begin();    while (it != boxs.end())    {        if (it->first != aim)        {            string path = printp(boxs[it->first]->path, boxs) + "->" + it->first;            outs.insert(pair<vertex, string>(it->first, path));        }        it++;    }    //outs已经存放好所有路径了    //打印数据    it = boxs.begin();    while (it != boxs.end())    {        if (it->first != aim)        {            cout << it->first + "\t最短路径：" + to_string(boxs[it->first]->dv) + "\t路径：" + outs[it->first] << endl;        }        it++;    }    return outs;} ## 评论
{"ft_lang_label":"__label__zh","ft_lang_prob":0.994323,"math_prob":0.9885423,"size":1549,"snap":"2020-34-2020-40","text_gpt3_token_len":1380,"char_repetition_ratio":0.09255663,"word_repetition_ratio":0.0,"special_character_ratio":0.2414461,"punctuation_ratio":0.06870229,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99566317,"pos_list":[0,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],"im_url_duplicate_count":[null,null,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-13T05:37:33Z\",\"WARC-Record-ID\":\"<urn:uuid:f6e6e6c3-da08-4242-b782-8895d394bab7>\",\"Content-Length\":\"470040\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7e73ecc0-143a-433b-8661-c7e5195446be>\",\"WARC-Concurrent-To\":\"<urn:uuid:2ddff34c-6510-4124-8ec0-02bc21ec2e16>\",\"WARC-IP-Address\":\"39.105.227.169\",\"WARC-Target-URI\":\"https://xie.infoq.cn/article/a528a3446f559d55e23cfcdae\",\"WARC-Payload-Digest\":\"sha1:BLDKW5MUMTD2DZPH3U4W5C3NQZGHXWCK\",\"WARC-Block-Digest\":\"sha1:5YUSTG2XWE6DCSNI4E2LXCVTE67FX2ER\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439738960.69_warc_CC-MAIN-20200813043927-20200813073927-00151.warc.gz\"}"}