戴克斯特拉(dijkstra )算法是单源最短路径问题的求解方法。 单源最短路径给出固定网络，指定原点s、目标点e，求出这两点之间的最短路径。 举板栗来理解一下吧。
淡淡的仙人掌上学的时候，从家到学校的路很多。 淡定的仙人掌为了减少在路上骑自行车的时间，想找到最短的路线。 他制作了以下网络图。
淡定的仙人掌是一个很爱动脑筋的同学，他开始研究如何才能找到最佳的出路。
1 )初始化所有点到家的距离：
2 )每次选择离家距离最短的点，用该点的距离更新其他相邻点到家的距离，小于当前点时更新节点值。
从所有点来看，V2离家最近，所以用V2更新与其相邻的点
v 3: min (10，35 )=8v6:min ) 312，INF )=15
3 )去掉V2这一点，在所有点中从家中寻找最小值点，发现V1最小，更新V1连接点V3、V4
v 3: min (8，4 )3)=7v4:min ) 4，8，INF )=12
4 )去除V1，继续寻找最小值的点V3，更新与V3相连的点V4 V5
v 4: min (12，10 )=10v5:min ) 712，INF=19
5 )去掉V3这一点，继续寻找最小值的点V4，更新与V4相连的点学校和V5
学校：min(105，INF )=15v5:min ) 19，103 )=13
6 )去掉V4这一点，继续寻找最小值的点V5，更新与V5相连的点学校
学校： min (15，13 )1)=14
6 )去掉V5，继续寻找最小值的点学校，更新学校连接点的空值。
迄今为止，淡定的仙人掌从家到学校最短距离为14，途经路径为家-V1-V3-V4-V5-学校。
上面的整个过程是dijkstra算法的中心思想，下面介绍了该过程。
1 ) dist[]存储第I个节点到家的距离，visited[i]=true表示第I个点是否通过。 2 )遍历所有visited[i]==false点，找到dist[i]最小的点k。 3 )遍历与k相连的点j，用min(dist[j]，dist[k] edge[k][j] )更新dist[j]。 4 )可视[ k ]=true； 5 )如果还有分，2 )练习实例代码)返回Dijkstra寻求最短路
给定n个点的m条边的有向图，图中可能存在重边和自环，所有边权为正值。 请求出从1号点到n号点的最短距离。 不能从1号点到n号点时输出-1。 输入格式的第一行包含整数n和m。 然后，m行中的每一行包含三个整数x、y和z，其中存在从点x到点y的有向边，边长为z。 输出格式输出表示1号到n号最短距离的整数。 路径不存在时输出-1。 数据范围为1n500，1m105，图中相关边长均在10000以下。 输入示例：3 31 2 22 3 11 3 4输出示例：实现3代码注释
# include stdio.h # include stdlib.h # include string.hint edges [ 550 ] [ 550 ]； //容纳所有边。 例如，edges[i][j]是从I到j的距离int dist[550]； int visited[550]，记录当前所有点到起点的距离； //标记当前点是否已被赶出intDijkstra(intn，int m ) for ) intI=1； i=n； I ) )//每个循环去除一个点，因此需要遍历for循环n次。 int索引=-1； //index表示距离当前未访问原点最近的点dist[1]=0。 //从原点到原点的距离为0，这很重要。 否则，以下for循环中的所有dist都是0x3f3f3f3f，找不到索引： for(intj=1； j=n； j () { //find the index of min distance if (！ visited [ j ] (index=-1|| dist [ j ] dist [ index ] ) /如果当前点未被踢出，且当前点的距离小于索引点的距离，则更新索引。 index==-1表示尚未找到dist最小值，并添加dist[1]。 索引=j； } }可见[索引]=1； //找到距离当前原点最小值的点后，标记点并踢出。 for(intj=1； j=n； j () if (dist [ index ] edges [ index ] [ j ] dist [ j ] ) { //index点更新与其关联的所有点。 dist [ j ]=dist [ index ] edges [ index ] [ j ]； }}if(dist[n]==0x3f3f3f3f ) /如果没有到n点的路径，则返回- 1； }返回dist [ n ]； }int main () memset ) Edges，0x3f，sizeof ) Edges )； int n，m； scanf('%d%d )，n，m )； for(intI=0； i m； I ) { int start，end，d； 扫描() %d%d )、开始、结束、d )； edges [ start ] [ end ]=edges [ start ] [ end ] d？ d : edges [开始] [结束]； //因为主题输入有重边，所以每次取最小值。 }memset(dist，0x3f，sizeof ) dist )； //初始化各dist的值是0x3f3f3f3f，memset是按字节设定的，各字节是0x3f，int是4字节，所以0x3f3f3f.memset(visited，0，sizeof ) visited //初始化所有点也没有被赶出去。 printf(%d(n )、dijkstra(n ) ) n、m )； 返回0； }