从入门角度深入理解——有关最短路的常见算法#1 最短路问题介绍
这里的最短路问题，指的是单源最短路。
单源最短路，意如其名，只有一个原点，走到其他点的最短路径。
即求一个点到其余点的最短路径。
图的简单概述：
要了解最短路，首先要简单理解一下什么是图。
书上概述如下（可以跳过不读）：
图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的顶点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把顶点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。
概念引入
可以简单的说，图是由一些点，和连接点的线组成。
点就是图的结点（顶点）。
线就是路径（边）。
（图1-1 简单的图）
关于边
同时，就像汽车走过一段路要消耗一定量的汽油，而消耗的汽油量跟边的长度有关一样。
边有一个属性，叫做边长（边权）。
（图1-2 有权图）
（图1-3 无权图）
跟道路一样，边有的时候只允许从A到B，不允许从B到A。
它具有方向是单行道（有向边），有的时候是双行道（无向边）。
根据有无 有向边，图分为有向图与无向图。
（两个点之间如果有两条有向边则可以当成有一条无向边，反之同样）
（所以在有向图中，不存在既包含有向边又包含无向边的说法，而全部边当成有向边处理。）
（图1-4有向图）
（图 1-5 无向图）
关于点
在无向图中，在一个点所连接的边的个数 称为度。
在有向图中，进入该点的边的个数为入度，从该点出去的边的个数为出度。
图1-5 中 3的度数为2
图 1-4 中 3的入度为2，出度为0
总结
图的元素有：
顶点（Vertex） 边（Edge）和 边权（Weight）
边分为有向边与无向边
扩展概念
-
边权 全为1的图叫做无权图，否则叫有权图。（如未说明权重，可视为无权图）
（图1-3 无权图）
（图1-2 有权图） -
路径：一系列由边相连的点，如1-7 中的 2，1，5，0是一条路径；4，3，2是一条路径。
（图 1-7） -
简单路径：不重复经过一个点两次的路径，如1-7中 2，1，5，0是一条简单路径，但2，1，5，0，1不是一条简单路径，因为1经过了两次。
-
回路：回路是一种路径，起点和终点相同的路径。如 1，5，0，1是一个回路，2，1，5，0，1，2也是一个回路。
-
简单回路：是只有起点和终点能重复两次的路径。如 1，5，0，1是一个简单回路，但2，1，5，0，1，2不是一个简单回路。因为除了起点2以外，1也被经过了两次。
-
环：不做特殊说明时，就是简单回路。
-
连通图：在无向图中，每两个点都可以相互到达。
-
子图：取原图中一部分的点和边构成的图
最短路的分类：
最短路问题
根据只有一个起点与多个起点
分为求单源最短路与多源最短路。
单源最短路是 已知一个起点，求出从该起点出发到其余点的最短的路径的长度是多少。
多源最短路是 已知一个图 求出所有点到所有点的最短的路径的长度。
此时最短路问题的分类情况很简单。
但具体的最短路问题中，最短路又分为很多种情况。
根据图的简单概述，我们知道图的分类情况。
有权图无权图 有向图无向图 有环图无环图
把他们简单地排列组合起来我们知道有八种情况
这里扩展一个概念
负环：指一个环内的所有边权相加小于0的环。
我们在求最短路问题时，要考虑负环。
负环存在与否的重要性甚至大于有向存在与否（在最短路算法中）。
所以我们把负环的情况考虑进去
这样一一列举出来，就有十种求最短路问题的情况。
这告诉我们，写最短路问题时要考虑：
1. 是否有权
2. 是有向图还是无向图
3. 是否有负环
逐个讲通常解法，不易懂，也没必要。所以考虑的解法情况可以分成这样：
在之后就会通过这些情况来了解最短路问题。
下一篇如何以入门级的基础理解常见最短路算法？#2 生动解释BFS与DFS、三种存图情况、STL的vector与pair（最短路算法的必要基础）