Weighted graph anhtt-fit@mail.hut.edu.vn Weighted Graph We can add attributes to edges. We call the attributes weights. For example if we are using the graph as a map where the vertices are the cites and the edges are highways between the cities. Then if we want the shortest travel distance between cities an appropriate weight would be the road mileage. If we are concerned with the dollar cost of a trip and went the cheapest trip then an appropriate weight for the edges would be the cost to travel between the cities. 1 Shortest Path Digraph G = (V,E) with weight function W: E → R (assigning real values to edges) Weight of path p = v1 → v2 → … → vk is k −1 w( p) = w(vi , vi +1 ) i =1 Shortest path = a path of the minimum weight Applications static/dynamic network routing robot motion planning map/route generation in traffic Shortest-Path Problems Shortest-Path problems Single-source (single-destination). Find a shortest path from a given source (vertex s) to each of the vertices. Single-pair. Given two vertices, find a shortest path between them. Solution to single-source problem solves this problem efficiently, too. All-pairs. Find shortest-paths for every pair of vertices. Dynamic programming algorithm. 2 Negative Weights and Cycles? Negative edges are OK, as long as there are no negative weight cycles (otherwise paths with arbitrary small “lengths” would be possible) Shortest-paths can have no cycles (otherwise we could improve them by removing cycles) Any shortest-path in graph G can be no longer than n – 1 edges, where n is the number of vertices Relaxation For each vertex v in the graph, we maintain v.d(), the estimate of the shortest path from s, initialized to ∞ at the start Relaxing an edge (u,v) means testing whether we can improve the

Lire le document entier