Weighted graph - jaredgorski.org

Weighted graph

data structures

A weighted graph is a Graph where each edge of the graph has some value associated with it. This value could represent the “strength” of the connection between two nodes, or perhaps the “cost” of traversing between two nodes, for example.

Implementation-wise, adding weights to a graph involves turning each item in the “connections array” into a tuple where the first element of the tuple represents the identity of the destination node and the second element of the tuple represents the weight of the connection.

A weighted graph implementation might look like this:

graph = {}
graph["chicago"] = [
  ("detroit", 1),
  ("st. louis", 3),
  ("minneapolis", 2)
]
graph["detroit"] = [
  ("chicago", 2),
  ("toronto", 1)
]
graph["st. louis"] = [
  ("chicago, 3),
  ("nashville", 4),
  ("tulsa", 2)
]
graph["nashville"] = [
  ("st. louis", 4),
  ("tulsa", 6),
  ("charlotte", 2)
]
graph["honolulu"] = []