最短路问题最短路问题最短（通）路问题是最重要最短（通）路问题是最重要的优化问题之一，例如各种管道的优化问题之一，例如各种管道的铺设、线路的安排、厂区的布的铺设、线路的安排、厂区的布局、设备的更新及运输网络的最局、设备的更新及运输网络的最小费用流等。（最短距离、费时小费用流等。（最短距离、费时最少、费用最省）最少、费用最省）破圈法是：任取一圈，去掉圈中最长边，直到无圈避圈法是：去掉图中所有边，从最短边开始添加，加边的过程中不能形成圈，直到连通（n－1条边）一个连通的无向图叫做树树无圈，但不相邻的两个点之间加一条边，得到一个圈树中任意两个顶点之间，恰有且仅有一条链下图中右图是支撑树v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)一个连通图能一笔画的条件是：它没有奇点；或者它恰好有一个奇点。一个图有5个点，８条边。这个图一定是A．连通图B．树C．完全图D．不连通图连通图G有n个点，其部分树是T，则有A.T有n个点n条边B.T的长度等于G的每条边的长度之和C.T有n个点n－1条边D.T有n－1个点n条边某人要从上海乘飞机到奥地利首都维也纳，他希望选择一条航线，经过转机，使他在空中飞行的时间尽可能短。该问题可转化为A.最短路线问题求解B.最大流量问题求解C.最小树问题求解D.中国邮递员问题求101099663311770022111155131322886611772222229911551111991144339977446633101099663311770022111155131322886611772222229911551111991144339977446633一般的最短路问题描述：一般的最短路问题描述：给定一个赋权有向图给定一个赋权有向图D=(V,A)D=(V,A)，对每一个弧，对每一个弧a=(va=(vii,v,vjj))，相应，相应地有权地有权ww(a)=(a)=wwijij，又给定，又给定DD中的任何两个顶点中的任何两个顶点vvss和和vvtt，设，设PP是从是从vvss到到vvtt的路，定义路的路，定义路PP的权是的权是PP中所有弧之和，记为中所有弧之和，记为ww(P)(P)，最短路问题就是要在所有从，最短路问题就是要在所有从vvss到到vvtt的路中，求一条权的路中，求一条权最小的路，即一条从最小的路，即一条从vvss到到vvtt的路的路PP00使得：使得：0P(P)min(P)路P0的权称为从vs到vt的距离，记为d(vs,vt)。DinkstraDinkstra标号法标号法这是解决网络中某一点到其它点的最这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法短路问题时目前认为的最好方法。。适用于有向图权值非负的情况适用于有向图权值非负的情况求网络上的一点到其它点求网络上的一点到其它点的最短路的最短路有向图权值非负有向图权值非负----Dijkstra----Dijkstra算法算法DijkstraDijkstra算法的基本步骤（权值非负）算法的基本步骤（权值非负）11、给顶点、给顶点vv11标号（标号（00），），vv11称为已标号点，记标号点集为称为已标号点，记标号点集为VV11={v={v11}}22、在未标号点集、在未标号点集VV22中找出与标号点集中找出与标号点集VV11中的顶点中的顶点vvii有弧相连（并且有弧相连（并且以以vvii为起点）的点为起点）的点vvjj，，33、在第、在第22步选出的点中，选出满足下面条件的点步选出的点中，选出满足下面条件的点vvkk，并给，并给vvkk标号标号（（ll,L,L1k1k），其中），其中ll为第一标号，为第一标号，LL1k1k为第二标号为第二标号11112minkllkiijijLLωLωvV,vV为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。5127563425527313571木器厂有六个车间，办事员经常要到各个车间了解生产木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图进度。从办公室到各车间的路线由图11给出。找出点给出。找出点11（办公室）到其它各点（车间）的最短路（办公室）到其它各点（车间）的最短路距离、价格距离、价格123252边边eeijij或记为（或记为（vvii，，vvjj））点（点（vvii））权权wwijij(d(dijij))0①①从点从点11出...
