最短路径
最短路径是一种思想不同于最小生成树的另一种图的应用，对网图来说，最短路径就是指两个顶点之间经过的边上权值和最小的路径，我们称第一个顶点为源点，最后一个顶点为终点（非网图边上没有权值，所说的最短路径就是两个顶点之间经过的边数最少的路径）。
此篇博客围绕Dijkstra算法展开，也就是从某个源点到图中其余各顶点的最短路径问题。
Dijkstra算法
Dijkstra算法通常被用来解决单源最短路径，它是由E.W.Dijkstra提出的一种按照路径长度递增的次序分别产生到
各顶点最短路径的贪心算法。
如图，我们要是求 顶点0 到 顶点1 的最短距离，这一眼就能看出来，就是 1 。
划重点，看黑板：
可以看到 顶点1 与顶点2,3,4有边，所以我们同时可以求出顶点0->1->2=1+3=4, 0->1->3=8,0->4=6
现在，如果要求顶点0 到顶点2 的最短路径，是 0 直接到 2 吗？显然不是，我们刚才求出的经过 顶点1 后到顶点2 的路径是4，所以 4 才是 顶点0 到 顶点2 的最短路径。
之后就是重复上述步骤，比如，顶点2 还与 顶点4,5有边，我们就可以得出顶点0->2->4=0->1->2->4=5,
0->2->5=0->1->2->5=11。那么此时，如果我们要求 顶点0 到 顶点4 的最短路径，是0->1->4=6吗，显然，刚才求出的0->1->2->4=5明显更短。
通过理解上述算法的思想，可以看出Dijkstra算法是一步步求出两个顶点之间顶点的最短路径，是基于已经求出的最短路径的路径上，求得更远顶点的最短路径
代码
void Dijkstra(Graph G, int V, int *P, int *W)
{
int book[MAXVEX]; //标记
int i, j, k, min;
bzero(book, sizeof(book));
book[V] = 1; //自己到自己不用求路径
W[V] = 0; //自己到自己为0
EdgeNode *e = G.adjList[V].firstedge;
while(e)
{
W[e->adjvex] = e->weight; //将与V有边的定点加上权值
e = e->next;
}
for(i = 0; i < G.vernum; ++i)
{
if(i == V) //跳过自己到自己
continue;
min = INF;
for(j = 0; j < G.vernum; ++j) //寻找离V最近的顶点
{
if(!book[j] && W[j] < min)
{
k = j; //存储最近顶点的下标
min = W[j]; //存储最近顶点的权值
}
}
book[k] = 1; //标记
e = G.adjList[k].firstedge; //更新当前最短路径及距离
while(e)
{
//如果经过V顶点的路径比现在这条路径的权值小就更新
if(!book[e->adjvex] && min + e->weight < W[e->adjvex])
{
W[e->adjvex] = min + e->weight;
P[e->adjvex] = k;
}
e = e->next;
}
}
}
采用的储存结构是邻接表（之前的博客有讲图的遍历——邻接表实现），有两个重要的数组P，W。
int Path[MAXVEX]; //储存最短路径下标
int ShortPathWeight[MAXVEX]; //储存到各点最短路径权值和
让我们来看一下运行结果：
我这里输入的是 顶点0 为源点：
Dijkstra(G, G.adjList[0].data, Path, ShortPathWeight);
理解一下：
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| Path-P | 0 | 0 | 1 | 4 | 2 | 4 |
| ShortPathWeight-W | 0 | 1 | 4 | 7 | 5 | 8 |
现在以求 顶点0 到 顶点5 的最短路径为例，P[5] = 4,意思是 顶点0 到 顶点5 的最短路径，顶点5 的前驱顶点是 顶点4，再由P[4] = 2, P[2] = 1, P[1] = 0, 可以得出 顶点0 到顶点5 的最短路径是:0->1->2->4->5。
然后我们再看ShortPathWeight数组，其最短路径是 8（0->1->2->4->5 = 1+3+1+3 = 8）。
最后
通过Path和 ShortPathWeight 数组，我们可以得到指定顶点到其他任意顶点的最短路径和最短路径长度。也就是说，我们通过Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题。通过代码我们可以看出它的时间复杂度为O(n^2)。
问：如果我们要求任一顶点到其余所有顶点的最短路径怎么办？
答：把每个顶点都当做源点运行一次Dijikstra算法。时间复杂度O(n^3)。
当然，Floyd算法也是解决此问题的方法之一。