1带权图的最短路径问题1、带权图的最短路径问题带权图的最短路径问题即求两个顶点间长度最短的路径。
其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。路径长度的的具体含义取决于边上权值所代表的意义。
【例】交通网络中常常提出的如下问题就是带权图中求最短路径的问题。两地之间是否有路相通?在有多条通路的情况下，哪一条最短?其中:交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。
2、交通网络的表示由于交通网络存在有向性，所以一般以有向网络表示交通网络。
【例】设A城到B城有一条公路，A城的海拔高于B城。若考虑到上坡和下坡的车速不同，则边和边上表示行驶时间的权值也不同。即和应该是两条不同的边。
3、源点和终点习惯上称路径的开始顶点为源点，路径的最后一个顶点为终点。为了讨论方便，设顶点集V=，并假定所有边上的权值均是表示长度的非负实数。单源最短路径问题单源最短路径问题：已知有向带权图G=，找出从某个源点s∈V到V中其余各顶点的最短路径。1、边上权值相等的有向网的单源最短路径用求指定源点的BFS生成树的算法可解决2、迪杰斯特拉算法求单源最短路径由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。按路径长度递增序产生各顶点最短路径若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成。
【例】在有向网G8中，假定以顶点0为源点，则它则其余各顶点的最短路径按路径递增序排列如右表所示
