最短路径Dijkstra算法实现【C++】

输 入 格 式 ： {color{Violet}输入格式：} 输入格式：

∙ bullet ∙ 第一行三个数n、m、start，分别代表城市个数、道路条数、出发点（起始点）。

∙ bullet ∙ 接下来m行每行三个数a、b、c，分别表示城市a、城市b、城市a和b之间的距离。

输 出 格 式 ： {color{Violet}输出格式：} 输出格式：

∙ bullet ∙ 输出一行n个数据，分别表示起始点start到该点的最短路径。

定 义 存 储 数 组 ： {color{Violet}定义存储数组：} 定义存储数组：

∙ bullet ∙ int road[max_city][max_city]，存储城市与城市之间的距离矩阵 ，初始化为无穷大。

∙ bullet ∙ int dist[max_city]，记录最短距离数组，初始化为无穷大。

∙ bullet ∙ bool visited[max_city]，记录是否已经被访问，初始化为false。

代 码 ： {color{Violet}代码：} 代码：

#include
using namespace std;

const int INF=99999999;  //自定义无穷大数
int road[1005][1005]; //记录距离矩阵
int dist[1005]; //记录最短路径数组
bool visited[1005]; //记录是否已经搜过

//dijkstra最短路径算法，参数为城市数目n、起始点start
void dijkstra(int n,int start)
{
    dist[start]=0;
    //依此遍历n个点，分别记录各点的最短路径
    for(int i=0;i>n>>m>>start;
    //初始化，都定义为无穷大
    fill(road[0],road[0]+1005*1005,INF);
    fill(dist,dist+1005,INF);
    //输入起点（a）、终点（b）、距离（c），并存入距离矩阵中
    for(int i=0;i>a>>b>>c;
        road[a][b]=c;
        road[b][a]=c;
    }
    //调用函数
    dijkstra(n,start);
    system("pause");
    return 0;

}

结 果 ： {color{Violet}结果：} 结果：