CSE 3500 Study Guide - Midterm Guide: Priority Queue, Sydney Trains S Set, Time Complexity
12 Dec 2019
School
Department
Course
Professor
Document Summary
Weighted graph - each edge has a numeric value ( a weight ) Length of a path - the sum of the weights of all edges in the path. Problem: what is the shortest path from a given start node to each one of the nodes in a weighted directed graph. G = (v, e) connected, weighted, (can be directed) graph with nonnegative weights. D(v) = distance from s to v. Set s to s and d(s) = 0. For all edges (u, v) from a node u s to a node v v - s (u is explored, v is not explored) Determine the distance d(v) from s to v, via u. Pick the node v with the shortest path from s. Add v to s v is now considered explored. Repeat until s = v all nodes have been explored. Store nodes in v with d"(v) for v v initialize d"(v) to infinity.
