图算法(二) 最短路经 Shortest Path Dijkstra算法练习题链接 /vjudge/contest/view.action?cid=29337#overview Floyd算法练习题链接 /vjudge/contest/view.action?cid=29305#overview 密码都是：671 /sjjg/DataStructure/DS/web/flashhtml/Dijkstra.htm 这个链接是Dijskra算法的动态演示 最短路径问题 最短路径问题 单源最短路径 Single-Source Shortest Path (Dijkstra算法) 单源最短路径 Single-Source Shortest Path 问题: 带权有向图G(E,V), 找出从给定源顶点s到其它顶点v的权最小路径。 “最短路径” = 最小权 路径的权是路径上所有边的权之和。 例：道路图 : 从青岛理工到金沙滩的最短路径? 单源最短路径 图中从v0到其余各顶点之间的最短路径: v0到 v1 无 v0到 v2 (v0 ,v2 ) 10 v0到 v3 (v0 ,v4 , v3) 50 v0到 v4 (v0 ,v4) 30 v0到 v5 (v0 ,v4 , v3 ,v5) 60 权非负的单源最短路径算法(Dijkstra) 贪心算法： 若顶点序列{V0,V1,…,Vn} 是从V0到Vn的最短路，则序列 {V0,V1,…,Vn-1} 必为从V0到Vn-1的最短路。 权非负的单源最短路径算法(Dijkstra) 基本思想： 将图中所有顶点分成两组:S, V-S 一组是包括已确定最短路径的顶点的集合S，另一组是尚未确定的最短路径的顶点集V-S。 S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。 权非负的单源最短路径算法(Dijkstra) 初始时,S仅包含源v0, 特殊路径： 从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。 步骤: (1) 取v0加入S中 (2) 从V-S中取出具有当前最短路径长度的顶点w加入S中。 权非负的单源最短路径算法(Dijkstra) 权非负的单源最短路径算法(Dijkstra) void init() // 对一些数据进行初始化 {int i , j; for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) grap[i][j] = INF; memset(pre , 0 , sizeof(pre)); } void dijkstra(int u) { int i , j; for(i = 1; i <= n; i++) //首先求出源点到其他所有点的距离 dist[i] = grap[u][i]; pre[u] = 1; int x = u; for(i = 1; i < n-1; i++) {int maxs = INF; for(j = 1; j <= n; j++) // 类似于最小生成树prim算法 ， 找到距离最短的那个点 if(!pre[j] && maxs > dist[j]) { maxs = dist[j]; x = j; } pre[x] = 1; for(j = 1; j <= n; j++) //然后再通过这个点去得到其他点的最短距离 if(!pre[j] && dist[j] > (dist[x]+grap[x][j]) && grap[x][j] < INF) dist[j] = grap[x][j] + dist[x]; } } int main() { scanf("%d %d" , &n , &m); init(); int i , x , y , z; for(i = 0; i < m; i++) //对有向图进行存储 { scanf("%d %d %d" , &x , &y , &z); grap[x][y] = z; } dijkstra(1); //假设求点1到其他点的最短路 return 0; } 所有顶点对之间的最短路径算法Floyd算法 已知一个有向图(无向图)，对于每对顶点Vi ！=Vj ，求出它们之间的最短路径

 
一、最短路径
 
最短路径：从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。
 
求最短路径的四个算法如下：
 
二、算法概述
 
【Dijkstra算法】
 
单源最短路：从单个源点出发，到所有结点的最短路
 
作用：计算正权图上的单源最短路。
 
图类型：有向图、无向图。
 
限制：边权为正。
 
【Bellman-Ford算法】
 
事实1：当负权存在时，连最短路都不一定存在。
 
事实2：如果最短路存在，一定存在一个不含环的最短路。
 
作用：计算图上的单源最短路(前提是最短路存在)。
 
图类型：有向图、无向图。
 
优势：边权可为负。
 
【Floyd算法】
 
作用：求出每两点之间的最短路。
 
图类型：有向图、无向图。
 
特点：如果要用Dijkstra或Bellman-ford求出每两点之间的最短路，那么需要调用n次Dijkstra(边权均为正)或者Bellman-ford(有负权)。
 
三、负权问题
 
如果一个图仅仅是存在负权，但不构成负权回路，又该如何？
 

 
Dijkstra 算法
 
观察上图，若 A 作为源点，在第一轮循环后，B 被标记数组标记，但我们发现在第二轮循环中，B 还可以通过 C 点继续进行更新。由此，可以得出结论：Dijkstra 算法不适用于负权图。
 
Bellman_Ford 算法和 SPFA 算法
 
我们先思考下上述 “因 B 点被标记数组标记而导致无法通过 C 点再更新” 的问题，归根结底是标记数组的锅。有人提议，不妨去掉标记数组，如果去掉，就会造成很严重的问题，首当其冲的是“无法求出dist[]的最小值”。
 
反观 Bellman_Ford 算法和 SPFA 算法，它们不存在标记数组的问题，因此对于仅仅存在负权的图，它们都可以工作的很好。
 
最后，读者需要注意的是，如果是无向图，只要存在一条负边，该图就存在负权回路，这不难理解，无向图的一条边相当于有向图的往返两条边。
 
四、补充分析
 
Dijkstra，Bellman_Ford 和 SPFA，该用哪个？
 

 
Bellman_Ford 没什么好说的，能不用就不用。
 
国际上一般不承认 SPFA 算法，因为在 SPFA 算法论文中对它的复杂度证明存在错误，其次 Bellman_Ford 的论文中已提及过这个队列优化。
 
SPFA 算法有两个优化策略 SLF 和 LLL。
 
SLF，Small Label First 策略，设要加入的节点是 j，队首元素为 i，若dist[j] < dist[i]，则将 j 插入队首，否则插入队尾；
 
LLL，Large Label Last 策略，设队首元素为 i，队列中所有 dist 值的平均值为 x，若dist[i] > x则将 i 插入到队尾，查找下一元素，直到找到某一 i 使得dist[i] <= x，则将 i 出队进行松弛操作。
 
SLF 可使速度提高 15 ~ 20%，SLF + LLL 可提高约 50%。 在实际的应用中 SPFA 的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法。
 
使用邻接表 + 二叉堆优化的 Dijkstra 算法，复杂度适宜，也稳定，就是有个缺陷，不能处理负权回路。
 
最后话个唠，我发现在算法竞赛中我们大多数的选择还是 SPFA，知乎了下，邻接表 + 二叉堆优化的 Dijkstra 写起来复杂，容易错，而 SPFA 代码简单，容易写，但是会被题目卡数据。
 
总结：首选 Dijkstra，其次 SPFA，最后 Bellman_Ford，具体采用哪种方法，视情况而定。

 
上一篇博文我们提到了图的最短路径问题：两个顶点间的最短路径该如何寻找？其实这个问题不应该叫“最短”路径问题，而应该叫“最便宜”路径问题，因为有时候我们会为图中的边赋权(weight)，也叫权重，相当于经过一条边的“代价”，一般为正数。比如下图(边旁的数字即该边的权重)
 

 
如果单纯考虑一条路径上边的条数，那么从v0到v6的最短路径应该是：v0-v3-v6。但是如果考虑边的权重，从v0到v6的“最便宜”路径应该是：v0-v1-v4-v6，其总权重为3(路径中所有边的权重之和)，而如果走v0-v3-v6的路径，总权重将是11。
 
边有权重的图我们称之为赋权图，反之称为无权图，赋权图显然可以比无权图应用于更多场合，比如用赋权图来表示城市间公路，权重越大路况越差，或者权重越大，过路费用越高等等。
 
其实不考虑权重的最短路径问题就是所有边的权重都是1的“最便宜”路径问题，比如将上图的所有边去掉权重后的无权图也可以这样表示：
 

 
方便起见，我们就将“最便宜”路径称为最短路径。
 
接下来让我们先从简单的无权情况开始，看看如何找两个顶点间的最短路径。不过到了这一步，一件有意思的事情需要说明一下，那就是：找X到Y的最短路径，比找X到所有顶点的最短路径更慢(有权无权都是如此)。
 
出现这个情况的原因我们可以简单的分析一波：找X到Y的最短路径，最直接的做法就是令程序从X出发沿着可行的边不断的走，直到走到Y处为止，但是当走到Y处时，没人能保证刚刚走的那条路就是最短的，除非你走遍了整个图的顶点，换句话说，你要确定走到Y处且走的路径是最短的，你就得走遍所有顶点，而且在这个过程中你必须不断记录各个路径的长度，不然当你发现到一个顶点有多条路径时怎么比较它们呢？所以，你要找X到Y的最短路径，你就得找出X到所有顶点的最短路径。
 
当然，也存在专门寻找点对点最短路径的思路，但是目前来说，单独找X到Y的最短路径不会比找X到所有顶点的最短路径更快，所以我们接下来探讨的问题其实都是：单源最短路径问题。即给定一个起点(源)，求出其与所有顶点的最短路径。有了到所有顶点的最短路径，我们自然也就有了到给定顶点Y的最短路径。
 
对无权图进行单源最短路径寻找的思路，就是我们上面所说的“最直接的做法”。为了更方便讲解，我们假定若存在边(A，B)，则B是被A“指向”的顶点。那么对无权图进行单源最短路径寻找就是这样的：
 
首先，我们将起点的路径长设为0，其他顶点路径长设为负数(也可以是其他不可能的值，图例中用？表示)，下例以v1作为起点
 

 
接着我们将起点所指向的顶点的路径长设为1，可以肯定的是，只有被路径长为0的起点所指向的顶点的路径长为1，本例中即v3和v4：
 

 
接下来，我们将路径长为1的顶点(v3和v4)所指向的顶点的路径长设为2，同样可以肯定，只有被路径长为1的顶点所指向的顶点的路径长为2。不过此时会遇到一个问题：v3是v4所指向的顶点，但v3的路径长显然不应该被设为2。所以我们需要对已知路径长的顶点设一个“已知”标记，已知的顶点不再更改其路径长，具体做法在给出代码时将写明。本例中，路径长要被设为2的顶点是v2、v5、v6：
 

 
然后我们继续这样的步骤，将路径长为2的顶点所指向的顶点的路径长设为3。不过本例中路径长为2的顶点所指向的顶点中已经没有未知顶点了，所以算法结束。
 
上述步骤随着图的规模变大而变多，但不难发现其规律就是：将路径长为i的顶点所指向的未知顶点的路径长设为i+1，i从0开始，结束条件即：当前路径长为i的顶点没有指向其它顶点，或所指向的顶点均为已知。
 
需要注意的是结束条件的说法，我们并没有要求所有顶点都变为已知，因为确定某顶点为起点后，是有可能存在某个顶点无法由起点出发然后到达的，比如我们的例子中的v0，不存在从v1到v0的路径。
 
接下来要做的事情就是用代码实现我们所说的思路，此时我们需要注意是我们并不想在图上直接动手脚，因为图可能还有他用，并且直接在图上动手脚也不方便，因为图中顶点可能并没有用于表示是否已知的域和用于表示从起点到自身的最短路径长的域。
 
所以我们的做法是将最短路径的计算结果存于一个线性表中，其结构如下：
 

 
其中“一行”为线性表中的一个元素，每一行的四个单元格就是一个元素中的四个域：顶点、是否已知、与起点最短路径长、最短路径中自身的前一个顶点。
 
那么之前计算最短路径的过程用这个表来表示的话，就是下面这样：
 

 

 

 
当我们想知道从起点到顶点Y的最短路径时，我们只需要找到Y顶点，查看其distance域即可知道，而想知道整条路径是怎么走的，我们也只要追溯Y的preV直到起点即可知道。下面是输出起点到给定终点的最短路径的一个例子：
 
//路径表中的元素定义，我们假设顶点vx即数字x，所以元素没有vertex域
 
structpathNode
 
{
 
boolknown;
 
intdistance;
 
size_t preV;
 
}
 
//路径表
 
structpathNode pathTable[numVertex];
 
void printPath(size_t end,struct node*pathTable)
 
{
 
size_t preV=pathTable[end].preV;if(pathTable[preV].distance!=0)
 
printPath(preV,pathTable);elseprintf("%d",preV);
 
printf("->");
 
printf("%d",end);
 
}
 
下面是上述无权最短路径思路的一个简单伪代码实现：
 
//无权最短路径计算，图存于邻接表graph，结果存入pathTable，起点即start
 
void unweightedPath(Node* graph,struct pathNode*pathTable,size_t start)
 
{
 
pathTable[start].known=true;
 
pathTable[start].distance=0; //若pathTable[x].distance为0，则其preV是无用的，我们不予理睬//初始化pathTable中的其他元素//curDis即当前距离，我们要做的是令distance==curDis的顶点所指的未知顶点的distance=curDis+1
 
for(int curDis=0;curDis
 
{for(int i=0;i
 
{if(!pathTable[i].known&&pathTable[i].distance==curDis)
 
{
 
pathTable[i].known=true;//遍历pathTable[i]所指向的顶点X
 
{if(!pathTable[X].known)
 
{
 
pathTable[X].preV=i;
 
pathTable[X].distance=curDis+1;
 
}
 
}
 
}
 
}
 
}
 
}
 
与上一篇博文的拓扑排序一样，上面的最短路径算法还有改进空间。当我们寻找符合distance==curDis条件的顶点时，我们用的是直接遍历数组的方法，这使得我们的算法时间复杂度达到了O(nv2)(nv为顶点个数)，所以我们要改进的就是“寻找符合条件的顶点”的过程。我们可以创建一个队列来存储“需要处理的顶点”，该队列初始时只有起点，当我们修改了某个未知顶点的distance后，我们就将该顶点入队，而当我们令curDis递增后再次寻找distance==curDis的顶点时，我们只需要令队列元素出队即可获取到想要的顶点。这个过程口述难以表达清楚，下面是应该足够清晰了的伪代码：
 
//无权最短路径计算，图存于邻接表graph，结果存入pathTable，起点即start
 
void unweightedPath(Node* graph,struct pathNode*pathTable,size_t start)
 
{//初始化pathTable//创建队列pendingQueue//将起点start入队
 
size_t curVertex;while(!empty(pendingQueue))
 
{
 
curVertex=Dequeue(pendingQueue);
 
pathTable[curVertex].known=true;//遍历curVertex指向的顶点X
 
{if(!pathTable[X].known)
 
{
 
pathTable[X].distance=pathTable[curVertex].distance+1;
 
pathTable[X].preV=curVertex;
 
Enqueue(X,pendingQueue);
 
}
 
}
 
}
 
}
 
这样一来，我们就将无权最短路径算法的时间复杂度由O(nv2)降低到了O(nv+ne)(ne即边的条数)。此外，上述算法对于无向有圈图也是一样生效的，原因就不赘述了，道理是简单的。
 
接下来的问题是如何对有权图进行单源最短路径的寻找。有权图的最短路径显然比无权图要难找，原因在于我们不能套用无权算法的思路，直接令已知顶点所指未知顶点的distance=curDis+weight(weight即两顶点间路径的权重，此处简写)，以下图为例：
 

 
若我们令v0作为起点，然后令v0所指的未知顶点的distance=v0.distance+weight，那么v3的distance就会变成5，可是实际上v3的distance应改为2。
 
解决的思路是：我们罗列出所有已知顶点指向的所有未知顶点，看这些未知顶点中谁的distance被修改后会是最小的，最小的那个我们就修改其distance，并认为它已知。
 
以上图为例，我们一步步走一遍来加深一下理解：
 
首先是正常的初始化(我们将边的权重也标识出来)，假设起点为v0：
 

 
接着我们罗列出所有已知顶点(只有v0)指向的所有未知顶点：v1、v2、v3。然后发现若修改它们的distance，则v1.distance=v0.distance+1=1，v2.distance=v0.distance+3=3，v3.distance=v0.distance+5=5。显然v1被修改后的distance是未知顶点中最小的，所以我们只修改v1的distance，并将v1设为已知，v2、v3不动：
 

 
接着我们继续罗列出所有已知顶点(v0、v1)指向的所有未知顶点：v2、v3、v4。然后发现若修改它们的distance，则v2.distance=v0.distance+3=3，v4.distance=v1.distance+1=2，v3.distance=v1.distance+1=2(虽然v0也指向v3，但是通过v0到v3的路径长大于从v1到v3，所以v3的distance取其小者)，其中v3和v4的新distance并列最小，我们任选其一比如v4，然后只修改v4的distance，并将v4设为已知，其它不动：
 

 
继续，我们罗列出所有已知顶点(v0、v1、v4)指向的所有未知顶点：v2、v3、v6，发现若修改，则v2.distance=3，v3.distance=2，v6.distance=3，所以我们只修改v3的distance，并将v3设为已知：
 

 
继续，我们罗列出所有已知顶点(v0、v1、v3、v4)指向的所有未知顶点：v2、v5、v6，发现若修改，则v2.distance=3，v5.distance=10，v6.distance=3，我们在v2和v6中任选一个如v2，只修改v2.distance，并将v2设为已知：
 

 
继续，我们罗列出所有已知顶点指向的所有未知顶点：v5、v6，发现若修改，则v5.distance=5，v6.distance=3，所以我们只修改v6：
 

 
最后，罗列出的未知顶点只有v5，若修改，其distance=5，我们将其修改并设为已知，算法结束：
 

 
其实上述算法的核心部分就是：
 
1.找到所有已知顶点
 
2.将所有已知顶点指向的所有未知顶点罗列出来
 
3.计算这些未知顶点的最小distance，然后再确定其中新distance最小的顶点X
 
4.只修改X的distance，并将X设为已知
 
5.回到第二步，若所有已知顶点都没有指向未知顶点，则结束
 
而这个算法就是Dijkstra算法的雏形。
 
Dijkstra算法核心部分简化的说法就是：找到所有可确定distance的未知顶点中新distance最小的那个，修改它并将它设为已知。
 
用伪代码描述就是这样：
 
//有权最短路径计算，图存于邻接表graph，结果存入pathTable，起点即start
 
void weightedPath(Node* graph,struct pathNode*pathTable,size_t start)
 
{//初始化pathNode数组
 
size_t curV;while(true)
 
{//找到可确定distance的未知顶点中新distance最小的那个，存入curV，若没有则跳出循环//令pathNode[curV].distance和pathNode[curV].prev修改为正确的值
 
pathNode[curV].known=true;
 
}
 
}
 
可以确定的是，Dijkstra算法也可以应用于无权图，只要给无权图中的每条边加个值为1的权重即可。并且如果你将无权算法与Dijkstra算法进行对比，就会发现那个无权算法其实就是Dijkstra算法的“特例”，在无权算法中，我们之所以不需要去找“distance最小的未知顶点”，是因为我们可以肯定已知顶点所指向的未知顶点就是“distance最小的未知顶点”。
 
不用想都知道，Dijkstra算法中的循环中的两行伪代码其实意味着大量的操作：找到可以确定distance的未知顶点，计算它们的distance，比较出最小的那个，修改……
 
显然，Dijkstra算法的核心部分是可以改进的，改进的思路与无权算法也很相像，即“加快寻找符合条件的顶点的过程”。其中一种改进方式是计算出未知顶点的新distance后，将{未知顶点，新distance}对插入到以distance为关键字的优先队列中，而不是直接抛弃非最小distance的那些未知顶点(这是一个很大的浪费)。这样在下一次寻找“distance最小的未知顶点”时，我们可以通过优先队列的出队来获得，从而避免了遍历整个数组来寻找目标的情况。这个想法要细化实现的话，还有不少坑要避开，不过我写到这儿时深感表达之困难与疲惫，所以这篇博文就此打住，如果博文中有什么不对之处，可以在评论区指出，谢谢~
 
附：如果有权图中存在权重为负值的情况，则计算单源最短路径将会更加困难，不过可以确定的是，如果有权图中存在圈与负权边，且负权边在圈中，使得圈的路径长为负，那么单源最短路径的计算是无法进行的，因为你可以在这个圈中永远走下去来使路径长不断“减小”。解决有负值权重边的图的最短路径算法是在Dijkstra的算法上进行改进得来的，本文不予讲解(或许以后会有一篇文章介绍)，有兴趣的可以自行搜索。

 
一：最短路径问题
 
(一)定义
 
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那条路径
 
1.这条路径就是两点之间的最短路径2.第一个顶点为源点3.最后一个顶点终点
 
(二)分类
 
单源最短路径--->有权，无权--->有向，无向
 
从某固定源点触发，求其到所有其他顶点的最短路径
 
多源最短路径
 
求任意两顶点间的最短路径
 
可以通过对每个顶点使用一次单源(不是最好)
 
二：无权图的单源最短路径(有向)
 
不考虑无向，无向我们使用BFS，进行层次遍历时，就可以获取
 
(一)定义
 
按照递增(非递减)的顺序找出各个顶点的最短路径
 

 
找出视图源点v3到每个顶点的最短路径
 

 
(二)思考
 
从上图路径表我们可以看出，其路径是按照BFS(有所不同)，使用队列进行递增访问各个顶点，从而遍历了所有顶点。
 
注意：这里我们不使用栈来实现，因为栈用到回溯法，而且使用栈不能很好找到最短路径长
 
(三)代码实现
 
创建邻接矩阵时看这个图　　　　　　　　　　　　　　　　进行结果对比用这个
 

 

 
void unWeight(MGraph G, ints)
 
{int dist[MAXVEX]; //记录达到下标对应顶点的最小距离
 
int path[MAXVEX]; //记录每个下标对应顶点的前一个经过的顶点
 
inti, v, w;//生成队列一会使用
 
LinkQueue Q;
 
InitQueue(&Q);for (i = 0; i < MAXVEX; i++)
 
dist[i]= -1; //全部初始化为-1，表示该顶点未被访问过，没有找到最短路径到这个顶点//将源点入队
 
EnQueue(&Q, s);
 
dist[s]= 0;
 
path[s]= s; //将这里设置为他自己是自己的上一步，因为后面根本不会去设置他了
 
while (!EmptyQueue(Q))
 
{
 
DeQueue(&Q, &v);for (w = 0; w < G.numVertexes; w++)
 
{if (G.arc[v][w] == 1) //找到邻接点w
 
{if (dist[w] == -1)
 
{
 
dist[w]= dist[v] + 1;
 
path[w]=v;
 
EnQueue(&Q, w);
 
}
 
}
 
}
 
}for (i = 0; dist[i] != -1; i++)　　//对各个顶点的最短路径长度进行打印，以及他的上一步路径也打印
 
{
 
printf("%d %c-%c\n", dist[i], G.vers[path[i]], G.vers[i]);
 
}
 
}
 

 
(四)全部代码
 

 

 
#pragma once#ifndef _QUEUE_H#define _QUEUE_H#include#include
 
#define OK 1
 
#define ERROR 0
 
#define TRUE 1
 
#define FALSE 0
 
#define MAXSIZE 100typedefintElemType;
 
typedefintStatus;
 
typedefstruct_qNode
 
{
 
ElemType data;struct _qNode*next;
 
}QNode,*QNodePtr;
 
typedefstruct{
 
QNodePtr front,rear;//队头队尾指针
 
}LinkQueue;
 
Status InitQueue(LinkQueue*Q);
 
Status EnQueue(LinkQueue*Q, ElemType e);
 
Status DeQueue(LinkQueue* Q, ElemType*e);
 
Status EmptyQueue(LinkQueue Q);
 
Status getHead(LinkQueue Q,ElemType*e);#endif
 
queue.h
 

 

 
#include "queue.h"Status InitQueue(LinkQueue*Q)
 
{if (!Q)returnERROR;
 
Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode));if (!Q->front)returnERROR;
 
Q->front->next =NULL;returnOK;
 
}
 
Status EnQueue(LinkQueue*Q, ElemType e)
 
{//尾插法
 
if (!Q)returnERROR;
 
QNodePtr q= (QNodePtr)malloc(sizeof(QNode));if (!q)returnERROR;
 
q->data =e;
 
q->next = (*Q).rear->next;
 
(*Q).rear->next =q;
 
Q->rear =q;returnOK;
 
}
 
Status DeQueue(LinkQueue* Q, ElemType*e)
 
{
 
QNodePtr q;if (!Q || !e || EmptyQueue(*Q))returnERROR;
 
q= Q->front->next;
 
Q->front->next = q->next;*e = q->data;if (Q->rear ==q)
 
Q->rear = Q->front;
 
free(q);returnOK;
 
}
 
Status EmptyQueue(LinkQueue Q)
 
{if (!Q.front->next)returnTRUE;returnFALSE;
 
}
 
Status getHead(LinkQueue Q,ElemType*e)
 
{
 
QNodePtr q;if(EmptyQueue(Q))returnERROR;
 
q= Q.front->next;*e = q->data;returnOK;
 
}
 
queue.c
 

 

 
#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include"queue.h"
 
#define MAXVEX 100 //最大顶点数
 
#define INFINITY 65535 //用0表示∞typedefchar VertexType; //顶点类型，字符型A,B,C,D...
 
typedef int EdgeType; //边上权值类型10,15,...//邻接矩阵结构
 
typedef struct{
 
VertexType vers[MAXVEX];//顶点表
 
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边表
 
int numVertexes, numEdges; //图中当前的顶点数和边数
 
}MGraph;//创建邻接矩阵
 
void CreateMGraph(MGraph*G);//显示邻接矩阵
 
voidshowGraph(MGraph G);//进行最小路径获取
 
voidunWeight(MGraph G);intmain()
 
{
 
MGraph MG;
 
CreateMGraph(&MG);
 
showGraph(MG);
 
unWeight(MG,2);
 
system("pause");return 0;
 
}//生成邻接矩阵
 
void CreateMGraph(MGraph*G)
 
{inti, j, k, w;
 
G->numVertexes = 7;
 
G->numEdges = 12;//读入顶点信息
 
G->vers[0] = 'A';
 
G->vers[1] = 'B';
 
G->vers[2] = 'C';
 
G->vers[3] = 'D';
 
G->vers[4] = 'E';
 
G->vers[5] = 'F';
 
G->vers[6] = 'G';
 
G->vers[7] = 'H';
 
G->vers[8] = 'I';//getchar();//可以获取回车符
 
for (i = 0; i < G->numVertexes; i++)for (j = 0; j < G->numVertexes; j++)
 
G->arc[i][j] = INFINITY; //邻接矩阵初始化//创建了有向邻接矩阵
 
G->arc[0][1] = 1;
 
G->arc[0][3] = 1;
 
G->arc[1][3] = 1;
 
G->arc[1][4] = 1;
 
G->arc[2][0] = 1;
 
G->arc[2][5] = 1;
 
G->arc[3][2] = 1;
 
G->arc[3][4] = 1;
 
G->arc[3][5] = 1;
 
G->arc[3][6] = 1;
 
G->arc[4][6] = 1;
 
G->arc[6][5] = 1;
 
}//显示邻接矩阵
 
voidshowGraph(MGraph G)
 
{for (int i = 0; i < G.numVertexes; i++)
 
{for (int j = 0; j < G.numVertexes; j++)
 
{if (G.arc[i][j] !=INFINITY)
 
printf("%5d", G.arc[i][j]);elseprintf("0");
 
}
 
printf("\n");
 
}
 
}void unWeight(MGraph G, ints)
 
{int dist[MAXVEX]; //记录达到下标对应顶点的最小距离
 
int path[MAXVEX]; //记录每个下标对应顶点的前一个经过的顶点
 
inti, v, w;//生成队列一会使用
 
LinkQueue Q;
 
InitQueue(&Q);for (i = 0; i < MAXVEX; i++)
 
dist[i]= -1; //全部初始化为-1，表示该顶点未被访问过，没有找到最短路径到这个顶点//将源点入队
 
EnQueue(&Q, s);
 
dist[s]= 0;
 
path[s]= s; //将这里设置为他自己是自己的上一步，因为后面根本不会去设置他了
 
while (!EmptyQueue(Q))
 
{
 
DeQueue(&Q, &v);for (w = 0; w < G.numVertexes; w++)
 
{if (G.arc[v][w] == 1) //找到邻接点w
 
{if (dist[w] == -1)
 
{
 
dist[w]= dist[v] + 1;
 
path[w]=v;
 
EnQueue(&Q, w);
 
}
 
}
 
}
 
}for (i = 0; dist[i] != -1; i++)
 
{
 
printf("%d %c-%c\n", dist[i], G.vers[path[i]], G.vers[i]);
 
}
 
}
 
无权最短路径全部代码
 
三：有权的单源最短路径算法(迪杰斯特拉Dijkstra算法)
 
(一)了解
 

 
从v1-v6最小为6，即v1-v4-v7-v6。不一定为经过顶点最小的路，和上面的无权最短路径不同
 
注意：我们不考虑负值圈
 

 
会导致一直循环，获取无穷收益。导致所有算法都失效
 
(二)解决方法
 
方法和上面的无权路径还是相似的，就是按照递增的顺序找出各个顶点的最短路
 
(三)迪杰斯特拉Dijkstra算法
 

 

 
#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include"queue.h"
 
#define MAXVEX 100 //最大顶点数
 
#define INFINITY 65535 //用0表示∞typedefchar VertexType; //顶点类型，字符型A,B,C,D...
 
typedef int EdgeType; //边上权值类型10,15,...//邻接矩阵结构
 
typedef struct{
 
VertexType vers[MAXVEX];//顶点表
 
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边表
 
int numVertexes, numEdges; //图中当前的顶点数和边数
 
}MGraph;//创建邻接矩阵
 
void CreateMGraph(MGraph*G);//显示邻接矩阵
 
voidshowGraph(MGraph G);//迪卡斯特拉算法，获取最短路径
 
void Dijkatra(MGraph G, ints);void Dijkatra(MGraph G,ints)
 
{int path[MAXVEX]; //是数组下标表示的顶点所经历的前一个顶点
 
int dist[MAXVEX]; //是数组下标表示的顶点的最小权值路径和//上面两个数组都有作用,和无权最短路径一致，但是无权最短路径可以使用dist是否被设置来判断一个顶点是否被访问，//但是这里无法使用，因为dist和普里姆算法中的lowcost一样，是使用贪心算法时，每到一个顶点，我们都会全部更新dist//所以我们需要另外一个数组来标志各个顶点是否被访问
 
intfinal[MAXVEX];inti,j,k,min;//对数据进行初始化
 
for (i = 0; i < G.numVertexes;i++)
 
{
 
final[i]= 0; //0表示该数组下标所表示的顶点未被访问
 
path[i] = 0; //初始化路径数组为0，表示当前每个都是独立的根节点
 
dist[i] = G.arc[s][i]; //这一步是重点：初始化路径数组的值为起始v0到各个点的权值
 
}
 
dist[s]= 0; //到源点自己的路径为0
 
path[s] = s; //设置源点的前一个顶点就是自己
 
final[s] = 1; //源点被访问过了//开始主循环，每次求的v0(s)到某个v顶点的最短路径
 
for (i = 0; i < G.numVertexes;i++)
 
{
 
min= INFINITY; //和普里姆算法相似
 
for (j = 0; j < G.numVertexes;j++) //由于是有向图所以都要从0开始，找到他的每个邻接点
 
{if (!final[j]&&dist[j]
 
{
 
k= j; //记录下该v到s点的下标和min最小路径
 
min =dist[j];
 
}
 
}
 
final[k]= 1; //将目前找到的距离v0(S)最近的顶点置为1
 
for (j = 0; j < G.numVertexes;j++) //修正当前最短路径即距离
 
{//修正方法就是循环k的每个邻接点,我们作为三角形来看，若是两边之和小于第三边，那我们原来找的那条直接的最短边就失效了，用这两条直接代替//所以我们将距离修改，路径设置为他的上一步k,
 
if (!final[j]&&(min+G.arc[k][j])
 
{//说明找到了更短的路径，修改dist和path数组
 
dist[j] = min + G.arc[k][j]; //修改当前路径长度
 
path[j] =k;
 
}
 
}
 
}for (i = 0; i
 
{
 
printf("%d %c-%c\n", dist[i], G.vers[path[i]], G.vers[i]);
 
}
 
}intmain()
 
{
 
MGraph MG;
 
CreateMGraph(&MG);
 
showGraph(MG);
 
Dijkatra(MG,0);
 
system("pause");return 0;
 
}//生成邻接矩阵
 
void CreateMGraph(MGraph*G)
 
{inti, j, k, w;
 
G->numVertexes = 7;
 
G->numEdges = 12;//读入顶点信息
 
G->vers[0] = 'A';
 
G->vers[1] = 'B';
 
G->vers[2] = 'C';
 
G->vers[3] = 'D';
 
G->vers[4] = 'E';
 
G->vers[5] = 'F';
 
G->vers[6] = 'G';
 
G->vers[7] = 'H';
 
G->vers[8] = 'I';//getchar();//可以获取回车符
 
for (i = 0; i < G->numVertexes; i++)for (j = 0; j < G->numVertexes; j++)
 
G->arc[i][j] = INFINITY; //邻接矩阵初始化//创建了有向邻接矩阵
 
G->arc[0][1] = 2;
 
G->arc[0][3] = 1;
 
G->arc[1][3] = 3;
 
G->arc[1][4] = 10;
 
G->arc[2][0] = 4;
 
G->arc[2][5] = 5;
 
G->arc[3][2] = 2;
 
G->arc[3][4] = 2;
 
G->arc[3][5] = 8;
 
G->arc[3][6] = 4;
 
G->arc[4][6] = 6;
 
G->arc[6][5] = 1;
 
}//显示邻接矩阵
 
voidshowGraph(MGraph G)
 
{for (int i = 0; i < G.numVertexes; i++)
 
{for (int j = 0; j < G.numVertexes; j++)
 
{if (G.arc[i][j] !=INFINITY)
 
printf("%5d", G.arc[i][j]);elseprintf("0");
 
}
 
printf("\n");
 
}
 
}
 
全部代码
 

 

 
void Dijkatra(MGraph G,ints)
 
{int path[MAXVEX]; //是数组下标表示的顶点所经历的前一个顶点
 
int dist[MAXVEX]; //是数组下标表示的顶点的最小权值路径和//上面两个数组都有作用,和无权最短路径一致，但是无权最短路径可以使用dist是否被设置来判断一个顶点是否被访问，//但是这里无法使用，因为dist和普里姆算法中的lowcost一样，是使用贪心算法时，每到一个顶点，我们都会全部更新dist//所以我们需要另外一个数组来标志各个顶点是否被访问
 
intfinal[MAXVEX];inti,j,k,min;//对数据进行初始化
 
for (i = 0; i < G.numVertexes;i++)
 
{
 
final[i]= 0; //0表示该数组下标所表示的顶点未被访问
 
path[i] = 0; //初始化路径数组为0，表示当前每个都是独立的根节点
 
dist[i] = G.arc[s][i]; //这一步是重点：初始化路径数组的值为起始v0到各个点的权值
 
}
 
dist[s]= 0; //到源点自己的路径为0
 
path[s] = s; //设置源点的前一个顶点就是自己
 
final[s] = 1; //源点被访问过了//开始主循环，每次求的v0(s)到某个v顶点的最短路径
 
for (i = 0; i < G.numVertexes;i++)
 
{
 
min= INFINITY; //和普里姆算法相似
 
for (j = 0; j < G.numVertexes;j++) //由于是有向图所以都要从0开始，找到他的每个邻接点
 
{
 
if (!final[j]&&dist[j]
 
{
 
k = j; //记录下该v到s点的下标和min最小路径
 
min =dist[j];
 
}
 
}
 
final[k]= 1; //将目前找到的距离v0(S)最近的顶点置为1
 
for (j = 0; j < G.numVertexes;j++) //修正当前最短路径即距离
 
{//修正方法就是循环k的每个邻接点,我们作为三角形来看，若是两边之和小于第三边，那我们原来找的那条直接的最短边就失效了，用这两条直接代替//所以我们将距离修改，路径设置为他的上一步k,
 
if (!final[j]&&(min+G.arc[k][j])
 
{
 
//说明找到了更短的路径，修改dist和path数组
 
dist[j] = min + G.arc[k][j]; //修改当前路径长度
 
path[j] =k;
 
}
 
}
 
}for (i = 0; i
 
{
 
printf("%d %c-%c\n", dist[i], G.vers[path[i]], G.vers[i]);
 
}
 
}
 
解释：
 
迪杰斯特拉算法和普里姆算法和上面的无权最短路径算法相似，前两个红线处也是重点。自己想想。
 
下面来看第三处
 
for (j = 0; j < G.numVertexes;j++) //修正当前最短路径即距离
 
{//修正方法就是循环k的每个邻接点,我们作为三角形来看，若是两边之和小于第三边，那我们原来找的那条直接的最短边就失效了，用这两条直接代替//所以我们将距离修改，路径设置为他的上一步k,
 
if (!final[j]&&(min+G.arc[k][j])
 
{//说明找到了更短的路径，修改dist和path数组
 
dist[j] = min + G.arc[k][j]; //修改当前路径长度
 
path[j] =k;
 
}
 
}
 
我们选取源点的第一次循环来讲解
 
1.首先：我们前面的代码已经确定了源点(0)的最短路径
 

 
例如上图：我们确定了v0点的最短距离是v0-v3是1，所以我们将final[3]=1
 
2.我们在第三处，for循环中，修正的最短距离，不是我们v3距离，而是我们v3的邻接点的最短距离。
 
原来我们的dist是：
 

 
现在我们的for循环将去修正他，修正的方法是：
 

 
因为v1未被标记，而且min(就是d(v0-v3))+d(v3-v1)=1+3大于原来的dist[1]=2,所以不予理会
 

 
因为v2未被标记，而且min(就是d(v0-v3))+d(v3-v2)=1+2小于原来的dist[2]=4,所以我们将他的距离修改，变为dist[2]=min+E(3,2)，将他的路径也做修正，他的是一个顶点变为v3,path[2]=3
 
修正后的dist数组是：
 

 
for (j = 0; j < G.numVertexes;j++) //修正当前最短路径即距离
 
{//修正方法就是循环k的每个邻接点,我们作为三角形来看，若是两边之和小于第三边，那我们原来找的那条直接的最短边就失效了，用这两条直接代替//所以我们将距离修改，路径设置为他的上一步k,
 
if (!final[j]&&(min+G.arc[k][j])
 
{//说明找到了更短的路径，修改dist和path数组
 
dist[j] = min + G.arc[k][j]; //修改当前路径长度
 
path[j] =k;
 
}
 
}
 
最后：说一句
 
有向图和无向图无非就是矩阵不对称而已，求最短路径几乎是一致的。所以不必考虑太多
 
Dijkstra算法解决了从某个顶点到其余各顶点的最短路径。其时间复杂度是O(n*2)
 
四：基于无向图的顶点加权Dijkstra算法
 

 

 
#define _CRT_SECURE_NO_WARNINGS#include#include#include
 
#define MAXVEX 100
 
#define INFINITY 65535 typedefcharVertexType;
 
typedefintEdgeType;
 
typedefstruct{
 
VertexType vers[MAXVEX];//顶点表
 
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵
 
int numVertexes, numEdges; //图中的顶点数和边数
 
}MGraph;//创建邻接矩阵
 
void CreateMGraph(MGraph*G);//显示邻接矩阵
 
voidshowGraph(MGraph G);//迪杰斯特拉算法，获取最短路径
 
void Dijkatra(MGraph G, int s);
 
头文件及及结构
 

 

 
//显示邻接矩阵
 
voidshowGraph(MGraph G)
 
{for (int i = 0; i < G.numVertexes; i++)
 
{for (int j = 0; j < G.numVertexes; j++)
 
printf("%6d", G.arc[i][j]);
 
printf("\n");
 
}
 
}
 
显示邻接矩阵
 
(一)创建拓扑图
 
void CreateMGraph(MGraph*G)
 
{inti, j;
 
G->numVertexes = 7;
 
G->numEdges = 12;//读入顶点信息
 
G->vers[0] = 'A';
 
G->vers[1] = 'B';
 
G->vers[2] = 'C';
 
G->vers[3] = 'D';
 
G->vers[4] = 'E';
 
G->vers[5] = 'F';
 
G->vers[6] = 'G';
 
G->vers[7] = 'H';
 
G->vers[8] = 'I';for (i = 0; i < G->numVertexes; i++)for (j = 0; j < G->numVertexes; j++)
 
G->arc[i][j] = INFINITY; //邻接矩阵初始化//创建了有向邻接矩阵
 
G->arc[0][1] = G->arc[1][0] = 2;
 
G->arc[0][3] = G->arc[3][0] = 1;
 
G->arc[1][3] = G->arc[3][1] = 3;
 
G->arc[1][4] = G->arc[4][1] = 5;
 
G->arc[2][0] = G->arc[0][2] = 4;
 
G->arc[2][5] = G->arc[5][2] = 5;
 
G->arc[3][2] = G->arc[2][3] = 2;
 
G->arc[3][4] = G->arc[4][3] = 2;
 
G->arc[3][5] = G->arc[5][3] = 8;
 
G->arc[3][6] = G->arc[6][3] = 4;
 
G->arc[4][6] = G->arc[6][4] = 2;
 
G->arc[6][5] = G->arc[5][6] = 3;//读入顶点信息
 
for (i = 0; i < G->numVertexes; i++)
 
G->arc[i][i] = 0;
 
G->arc[1][1] = 4;
 
G->arc[2][2] = 2;
 
G->arc[3][3] = 10;
 
G->arc[4][4] = 1;
 
G->arc[5][5] = 3;
 
}
 
(二)实现基于顶点加权算法
 
void Dijkatra(MGraph G, ints)
 
{int path[MAXVEX]; //是数组下标表示的顶点所经历的前一个顶点
 
int dist[MAXVEX]; //是数组下标表示的顶点的最小权值路径和//上面两个数组都有作用,和无权最短路径一致，但是无权最短路径可以使用dist是否被设置来判断一个顶点是否被访问，//但是这里无法使用，因为dist和普里姆算法中的lowcost一样，是使用贪心算法时，每到一个顶点，我们都会全部更新dist//所以我们需要另外一个数组来标志各个顶点是否被访问
 
intfinal[MAXVEX];inti, j, k, min;//对数据进行初始化
 
for (i = 0; i < G.numVertexes; i++)
 
{
 
final[i]= 0; //0表示该数组下标所表示的顶点未被访问
 
path[i] = 0; //初始化路径数组为0，表示当前每个都是独立的根节点
 
dist[i] = G.arc[s][i]; //这一步是重点：初始化路径数组的值为起始v0到各个点的权值
 
}
 
dist[s]= 0; //到源点自己的路径为0
 
path[s] = s; //设置源点的前一个顶点就是自己
 
final[s] = 1; //源点被访问过了//开始主循环，每次求的v0(s)到某个v顶点的最短路径----(找到距离源点s,并且没有被访问过的顶点的最近顶点)
 
for (i = 0; i < G.numVertexes; i++)
 
{
 
min= INFINITY; //和普里姆算法相似
 
for (j = 0; j < G.numVertexes; j++) //由于是有向图所以都要从0开始，找到他的每个邻接点
 
{if (!final[j] && dist[j] < min) //若是该顶点没有被访问过，且该点到s点的距离小于min,我们就将min设置为他
 
{
 
k= j; //记录下该v到s点的下标和min最小路径
 
min =dist[j];
 
}
 
}
 
final[k]= 1; //将目前找到的距离v0(S)最近的顶点置为1
 
for (j = 0; j < G.numVertexes; j++) //修正当前最短路径即距离
 
{//修正方法就是循环k的每个邻接点,我们作为三角形来看，若是两边之和小于第三边，那我们原来找的那条直接的最短边就失效了，用这两条直接代替//所以我们将距离修改，路径设置为他的上一步k,
 
if (!final[j] &&k!=j&&(min + G.arc[k][j]+G.arc[k][k]) 
 
{//说明找到了更短的路径，修改dist和path数组dist[j] = min + G.arc[k][j] + G.arc[k][k]; //修改当前路径长度，是加上途经的顶点权值
 
path[j] =k;
 
}
 
}
 
}for (i = 0; i < G.numVertexes; i++)
 
{
 
printf("%d %c-%c\n", dist[i], G.vers[path[i]], G.vers[i]);
 
}
 
}
 
(三)结果显示
 
intmain()
 
{
 
MGraph MG;
 
CreateMGraph(&MG);
 
showGraph(MG);
 
Dijkatra(MG,0);
 
system("pause");return 0;
 
}