MAT344H1 Lecture Notes - Lecture 11: Negative Number
Document Summary
Length of a path (in this context) = sum of the cost of all edges along the path. We can define an algorithm that always give best possible answers. The idea is to start by learning shortest paths to nearby vertices and. Each vertex b is labelled with (x, a), where x is the last step vertex from i to j and a is the length of the shortest path from i to b. To label the graph, let m = 0. If any vertex b is adjacent to a labelled vertex w= (?, d(w)) and k(w, v) + d(w) = m. After having labelled all vertices this way, m = m+1 and we repeat. In the example, we label i by (-, 0), and label c by (i, 1) .
