CSE 214 Lecture Notes - Lecture 38: Travelling Salesman Problem, Adjacency Matrix, Linked List
2 Feb 2017
School
Department
Course
Professor
Document Summary
Some graphs have an associated weight assigned to each edge. Possible problems to solve using weighted graphs: shortest path between nodes, minimal spanning tree, etc. Examples include finding the shortest path from destination a and b, flight connections (shortest or cheapest), internet routing, etc. Minimal spanning tree - finding the shortest path to get to every single node. The total distance taken is at a minimum. Examples include: the traveling salesman problem is an application for this, utility lines, network connections, water, electricity, delivery trucks. Given a graph, you create an adjacency with the weights for each edge in the graph. 1 is used to denote that there are not connections between 2 nodes, not 0 in this case. We would use an array with a linked list in each element that denotes the multiple edges connected to other nodes (edge list).
