Search⌘ K
AI Features
Home
Courses
Learn Graph Algorithms in C++

Weighted Graphs

Explore the concept of weighted graphs where each edge has an assigned weight representing values like distance. Understand how these weights influence path lengths, differentiating weighted graphs from unweighted ones, and how this model applies to problems in graph theory and algorithms.

We'll cover the following...

Introducing weighted graphs

Weighted graphs are a slight generalization of graphs that are useful for modeling more complex problems using graph theory. In an (edge)-weighted graph, each edge is assigned a weight, which is usually a number that represents a property of the edge.

For example, consider this undirected graph of subway stations, where each edge represents a train connection. The weight of an edge is a real number representing the distance between the two nodes it connects.

g a Piccadilly Circus d Holborn a:se--d:w 1 e Embankment a:ne--e:w 0.7 f Baker Street a--f 1.6 b Liverpool Street c King's Cross c--b 2.4 c--d 1.3 d:e--b:sw 1.8 e:e--b:nw 2 f--c 1.7
A weighted graph where the edge weights are distances between subway stations.

Formally, a weighted graph G=(V,E,w)G = (V, E, w) is a graph with nodes VV, edges EE and an additional edge weight function ...