问题描述 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式 输出一个整数，表示 1 号点到 n 号点的最短距离。

迪杰斯特拉（Dijkstra ）算法： 对于图G=(V,E)，将图的顶点分为两组： 顶点集S：已求出的最短路径的顶点集合（初始为{v0}）； 顶点集V-S：尚未求出最短路径的顶点集合（初始为V-{v0} ）。 算法按最短路径长度的递增顺序逐个将V-S的顶点加入S中，直到所有顶点均被加入S为止。 算法需借助辅助数组dist[N]， dist[i]表示目前已经找到的、从开始点v0到终

通路总数 = 邻接矩阵所有元素的之和 回路总数 = 邻接矩阵对角线元素之和

本篇用于记录我在做图的最短路径的问题过程中学到的算法，如果有不足之处，还请指出。 关于图的最短路径，有四种算法，分别是普利姆算法，迪鲁斯卡尔算法，弗洛伊德算法和贝尔曼福特算法，接下来将对这些算法依次进行讲解。 1.普利姆算法 普里姆算法（Prim算法），是图论中的一种算法，可在加权连通图里搜索最小生成树，也就是求最小权值，最后生成的路径（也就是两个点之间的路径个数）个数比点少一，比如下面的图