[Data Structure] Weighted Graphs

A weighted graph associates a weight with each edge.

A graph edge's weight, or cost, represents some numerical value between vertex items, such as flight cost between airports, connection speed between computers, or travel time between cities. 

A weighted graph may be directed or undirected. 

 

Undirected Weighted Graph; Connection Speed Ex

 

 

In a weighted graph, the path length is the sum of the edge weights in the path. 

 

 

The cycle length is the sum of the edge weights in a cycle. 

A negative edge weight cycle has a cycle length less than 0. 

A shortest path doesn't exist in a graph with a negative edge weight cycle, because each loop around the negative edge weight cycle further decreases the cycle length, so no minimum exists. (minimum = -∞)