一、最短路径
①在非网图中，最短路径是指两顶点之间经历的边数最少的路径。
AE：1 ADE：2 ADCE：3 ABCE：3
②在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。
AE：100 ADE：90 ADCE：60 ABCE：70
③单源点最短路径问题
问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。
应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。
④每一对顶点之间的最短路径
问题描述：给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。
解决办法1：每次以一个顶点为源点，调用Dijkstra算法n次。显然，时间复杂度为O(n3)。 解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。
①基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。
②设计数据结构 :
1、图的存储结构：带权的邻接矩阵存储结构 。
2、数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。
3、数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。
4、数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。
③Dijkstra算法——伪代码
1. 初始化数组dist、path和s； 2. while (s中的元素个数<n) 2.1 在dist[n]中求最小值，其下标为k； 2.2 输出dist[j]和path[j]； 2.3 修改数组dist和path； 2.4 将顶点vk添加到数组s中；
①基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。
②设计数据结构
1、图的存储结构：带权的邻接矩阵存储结构 。
2、数组dist[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式：
3、数组path[n][n]：存放从vi到vj的最短路径，初始为path[i][j]="vivj"。
