图(a)所示网的计算结果:
4. 最短路径：最短路径问题是图研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个公路网，给定了该网内的n 个城市以及这些城市之间的相通公路的距离，能否找到城市A 到城市B 之间一条举例最近的通路呢？
如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网图中，求点A 到点B 的所有路径中，边的权值之和最短的那一条路径。这条路径就是两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。
单源点的最短路径问题：给定带权有向图G＝（V，E）和源点v∈V，求从v 到G 中其余各顶点的最短路径。在下面的讨论中假设源点为v0。
解决问题的迪杰斯特拉算法：
即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。
