这是我参与11月更文挑战的第10天，活动详情查看：2021最后一次更文挑战
最短路径 带权路径长度：从一个顶点v0到图中任意一个顶点vi的一条路径（可能有多种选择到达vi）所经过边上权值的和 其中带权路径长度最短的那条称为最短路径
1.利用Dijkstra算法求单源最短路径 先看一个例子来引入Dijkstra算法
（图片来源于网上）
我们选择从1开始 计算到2，3，4，5，6的最短路径
-
1->2 备选路径有：（1,2）=1
-
从1到3，4，5，6，且加入2进行辅助，目前能确定最短的是(1,2)+(2,4)=4 其他路径都比较大1->4 选择 (1,2)(2,4)
-
1到3，5，6的路径，现在可以加入2，4进行辅助，(1,2)+(2,4)+(4,3)=8,其他路径到3的都比8大 路径1->3选择 (1,2)(2,4)(4,3)
-
1到5，6的路径，现在可以加入2，3，4进行辅助(1,2)+(2,4)+(4,3)+(3,5)=13 其他路径到3的都比13大 路径1->5选择 (1,2)(2,4)(4,3)(3,5)
-
最后一个1到6 (1,2)+(2,4)+(4,3)+(3,5)+(5,6)=17 其他路径到3的都比17大 路径 1->6选择 (1,2)(2,4)(4,3)(3,5)(5,6)
在实现上面的这个过程中，进一步思考：
从v0出发到每个顶点的最短路径长度由什么存储（用一个数组）：dist[] 表示从v0到各个点的最短路径长度，初始状态就是v0直接到每个顶点的距离；
如何知道这个最短路径的顶点序列呢 则就需要path数组用来记录表示从源点v0到顶点vi之间的最短路径上的最后一条边的除顶点vi外的另一个顶点
如何知道我们的结点那些是未被确定的呢？s[i]=0表示顶点vi未确定最短路径，s[i]=1表示顶点vi已确定最短路径
代码实现：（邻接矩阵表示法）
void Dijkstra(Grapha G, int v) { //图G中从顶点v到其他顶点的单源最短路径
int dist[G.vexnum];
int path[G.vexnum];
int s[G.vexnum];
for(i=0; i<G.vexnum;i++){
dist[i] = G.edge[v][i];
s[i] = 0;
if(G.edge[v][i]<Max){ //Max可以随意设置一个最大值
path[i]=v;
}else {
path[i]=-1; //设为最大值即也理解为v到vi不可直接到达
}
}
s[v]=1; //源点值直接初始化为1；
path[v]=-1;
for(int i=0;i<G.vexnum;i++){ //一次循环 就确定一个v0到某个顶点的最短路径
int Min = Max; //这只是一个初始的参考值 min会随时变化
int u ; //v0到j点最小路径的下标
for(int j=0;j<G.vexnum;j++){ //这一个循环时在找从v0到每个结点的最短路径
if(s[j]==0 && dist[j]<min){
min = dist[j];
u = j;
}
}
s[u]=1; //找到那个到某个顶点的最短路径顶点u
for(int j=0; j<g.vexnum; j++){ //这个循环时更新dist，path数组 因为当选择了一个顶点的最短路径之后 那么这个顶点就可以加入v0顶点进行辅助 可能会有比直接到vi更短路径
if(s[j]==0 && dist[u]+G.edge[u][j] < dist[j]){
dist[j] = dist[u]+G.edge[u][j];
path[j] = u;
}
}
}
}
时间复杂度：O(|V|2)
但是 若权值是负数？则是这个方法计算就会出现问题，所以就出现了Floyd算法，后面会分享Floyd算法
