最短路径问题，一个经典算法问题。本文粗略总结了一种常见的最短路径算法，以及几个最短路径变种问题的解法，其中包括哈密顿路。对于有向图或者无向图，假设有V个节点，E条边，G[Vi,Vj]表示图中点Vi到Vj边的权值。dist[i]表示：点s到点i的最短路径。

一、单源最短路径

给定图G，求点对s->t之间的最短路径，该问题使用经典的dijkstra算法即可解决，时间复杂度O(V^2)。基本思想：两个集合S,T，S表示已经访问的点集合，T表示未访问的点集合，S初始为空，T包括所有点；每次从T集合中选取从s到该点距离最小的点cur，然后将点cur加入到S中(保证从s到S集合中的点之间的路径长度最小)，并且基于cur点为跳板，做松弛操作，更新s到T集合中其他点的距离，松弛操作即，如果dist[j]

> dist[cur] + G[cur,j]，更新dist[j] =

dist[cur]+G[cur,j]，其中j属于T集合；当cur==t时算法结束。

二、有负权边的图的单源最短路径

对于(一)中的dijkstra算法，是否可以用于求解带负权边的单源最短路径问题呢？用三元组(x,y,w)表示一条边权为w的从点x到点y的有向边。先举例看看，假设图中包含3个节点，包含3条边：(1，2，-3)、(2，3，1)、(3，1，1)，从图可以看出为一个环1->2->3->1，且环的边权总权值为-3+1+1=