最短路径

最短路径是一种思想不同于最小生成树的另一种图的应用，对网图来说，最短路径就是指两个顶点之间经过的边上权值和最小的路径，我们称第一个顶点为源点，最后一个顶点为终点（非网图边上没有权值，所说的最短路径就是两个顶点之间经过的边数最少的路径）。

此篇博客围绕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算法也是解决此问题的方法之一。

转载地址：http://gjqwi.baihongyu.com/

你可能感兴趣的文章

Android学习笔记（四六）：互联网通信-文件下载