白鸽

用户名：zhx123

访问量：61527

签　名：

一个认真的求学者

等　　级
排　　名	25
经　　验	16738
参赛次数	4
文章发表	280
年　　龄	25
在职情况	学生
学　　校	内蒙古大学
专　　业	软件工程（研究生）

　　自我简介：

爱笑的人运气都不会太差，因为运气差的人总是没有笑容

TA的其他文章

求最大值-题解(C++代码)
浏览：203

后缀子串排序-题解(C语言代码)
浏览：352

字符串的反码-题解(C++代码)
浏览：269

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解(C++代码) 完全是模仿手工算的时候的做法，尽管有些麻烦，但是实现了啊！！

　　作者: 白鸽　　　　发表时间：2020-04-11 21:52:52 浏览：553　|　评论：0　

原题链接：数据结构-Dijskra(迪杰斯特拉)最短路径算法

把我的代码中的注释打开，就可以看到过程了
```cpp
#include <iostream>
using namespace std;
int main(){
    int m,n;//m是有多少个顶点，n是从哪个顶点开始
    cin>>m>>n;
    int p[m][m];
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cin>>p[i][j];
        }
    }
    int d[m];//用来存储n顶点到其他顶点的最短路径，输出从1到m-1的数，默认是0
    for(int i=0;i<m;i++){
        d[i]=0;
    }
    //要想得到其他最短路径，需要循环m-1次，每次确定一个最短路径
    int k=m-1;
    int v[m];//看是否已经确定是最短路径了，初始化为0如果是1标识确定了
    for(int i=0;i<m;i++){
        v[i]=0;
    }
    int p1=n;
    int min;
    int min_i;
    bool b=true;
    for(int i=0;i<m;i++){
        if(i==n){
            continue;
        }
        if(p[n][i]!=0&&b){//找到第一个非0的元素标识为最小的
            min=p[n][i];
            min_i=i;
            b=false;
            d[i]=p[n][i];
        }
        if(!b&&p[n][i]!=0){
            if(p[n][i]<min){
                min=p[n][i];
                min_i=i;
            }
            d[i]=p[n][i];
        }
    }
    v[min_i]=1;//标识确定了最短路径的下标
    n=min_i;//有最小的从最小的那个开始，和上一次的d[i]对比，看是否有比他小的
    k=k-1;
//    cout<<n<<endl;
//    for(int i=0;i<m;i++){
//        cout<<d[i]<<" ";
//    }
//    cout<<endl;
    while(k--){//进行m-1次遍历，确定最小
        for(int i=0;i<m;i++){
            if(v[i]==1||i==p1){
                continue;
            }
            if(p[n][i]!=0&&d[i]!=0){
                if(p[n][i]+d[min_i]<d[i]){
                    d[i]=p[n][i]+d[min_i];
                }
            }
            if(p[n][i]!=0&&d[i]==0){
                d[i]=p[n][i]+d[min_i];
            }
        }
        b=true;
        //确定d[i]不为0的最小下标并且v[i]==0的下标
        for(int i=0;i<m;i++){
            if(d[i]!=0&&b&&v[i]==0){//找到第一个非0的元素标识为最小的
                min=d[i];
                min_i=i;
                b=false;
            }
            if(!b&&d[i]!=0&&v[i]==0){
                if(d[i]<min){
                    min=d[i];
                    min_i=i;
                }
            }
        }
        v[min_i]=1;
        n=min_i;
//        for(int i=0;i<m;i++){
//            cout<<d[i]<<" ";
//        }
//        cout<<n<<endl;
    }
    for(int i=0;i<m;i++){
        if(i!=p1){
            if(d[i]==0){
                cout<<-1<<" ";
            }else{
                cout<<d[i]<<" ";
            }
        }
    }
    return 0;
}

```

0.0分

2 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

白鸽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C二级辅导-同因查找（C语言代码）

一个简单易懂的代码

C二级辅导-统计字符（C语言代码）

【绝对值排序】（C++代码）

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解(C++代码) 完全是模仿手工算的时候的做法，尽管有些麻烦，但是实现了啊！！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

有关字符，字符串的输入输出函数说明

1054题解

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

白鸽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C二级辅导-同因查找 （C语言代码）

一个简单易懂的代码

C二级辅导-统计字符 （C语言代码）

【绝对值排序】 （C++代码）

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解(C++代码) 完全是模仿手工算的时候的做法，尽管有些麻烦，但是实现了啊！！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

有关字符，字符串的输入输出函数说明

1054题解

数组输出 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C二级辅导-同因查找（C语言代码）

C二级辅导-统计字符（C语言代码）

【绝对值排序】（C++代码）

　　评论区

数组输出（C语言代码）