NetworkOptimization.ppt

Network Optimization Chapter 3 Shortest Path Problems 3.1 Shortest paths from a single source In a weighted digraph, a path of minimum weight from vertex v to vertex w is called a shortest path (SP) from v to w, and its length is called the shortest distance (SD) from v to w. For undirected graph, we can define SP and SD between two vertices. The shortest path problem can be treated as a transshipment problem. 3.1 Shortest paths from a single source (a) If we want to find SP and SD from v to w， then: let v be the only source with a supply of 1 unit; let w be the only sink with a demand of 1 unit; let other vertices be intermediate vertices; let the cost of sending one unit of the commodity from i to j be the weight of the arc (i , j); we now use the network simplex method to solve this transshipment problem. A 0-1 solution x* will be obtained, and the arcs (i , j) with =1 form a shortest path from v to w. 3.1 Shortest paths from a single source (b) if we want to find shortest paths from a given vertex v to each of the other n-1 vertices in the digraph, then: let v be the only source with a supply of n-1 units; let every other vertex be a sink with a demand of 1 unit; let the cost of sending one unit of commodity from i to j be the weight of the arc (i , j); then the shortest path problem is transformed to a transshipment problem, and hence can be solved by the network simplex method. 3.1 Shortest paths from a single source We study other two algorithms: Dijkstra’s algorithm to find a SP and the SD from a specified vertex to every other vertex; Floyd and Warshall algorithm for all-pairs shortest path problem. Main idea about the Dijkstra’s method Suppose the 5 nearest vertices to v1 are v1,v3,v5,v7 and v9. Then finding the sixth nearest vertex is easy. Assume the sixth nearest vertex is v6 and the shortest path is (v1,…v?, v6). Then v? must be one the 5 nearest vertices. Can you see why? Another important idea!! Suppose 1356 is the SP