第十讲 最短路模型
（教材：第十章 最短路模型）
一. 有向图及最短有向路
二. Dijkstra 算法
三. 最短路模型及可以化为最短有向路问题的实际问题例子
一. 有向图及最短有向路
有向弧和有向图：对图中的每条边指定一个方向，就称边为有向弧或有向边，对应的图称为有向图。边没有方向的图称为无向图。用 
表示有向图，其中 
表示图的顶点集，
表示图的有向弧集。
如上图中的有向弧
，记为 
，
称为 
的头，
称为 
的尾。
有向子图：如果有向图 
是 
的一部分，即 
的顶点和有向弧是 
的顶点和有向弧的一部分：
，则称有向图 
是 
的有向子图。
底图、定向图：一个有向图的底图是指保留所有顶点、所有边但不考虑边方向后所得到的无向图。反之，对一个无向图，如果我们给每条边指定方向，这样得到的有向图称为原来图的定向图。
有向链、有向闭链、有向路、有向圈：这些概念都可以从无向图的有关概念得到。注意这里的链或路都是由首尾相连的有向弧组成。
双向连通，顶点的入次和出次：
称 
和 
双向连通，是指从 
到 
有一条有向路，同时从 
到 
也有一条有向路。顶点的入次指的是以该点为头的有向弧的数目，顶点的出次指的是以该点为尾的有向弧的数目。
有向网络、有向路的权和最短有向路：
对有向图中每条有向弧赋以权数，就得到有向网络。以
记一个有向网络，其中 
表示 
中有向弧对应的权，即对每条有向弧 
： 
，有一个称为权的实数 
与之对应。
有向路 
的权是 
中所有弧的权之和，有时也称为 
的长度， 记为 
。
给定有向网络
中的两个顶点 
，在 
到 
的所有有向路中，权最小的路称为从 
到 
的最短有向路。
求最短路的问题是指：求一条从
到 
的有向路 
，使 
，式中 min 为对 
中所有从 
到 
的有向路 
取最小，称 
是从 
到 
的最短路。路 
的权称为从 
到 
的距离，记为 
。一般，
与 
不一定相等。