weighted graph
A graph in which every edge carries a number, its weight, such as a distance, cost or travel time.
In more detail
In an adjacency list, weighted edges are stored as (neighbour, weight) tuples; in a matrix, each cell holds the weight instead of a 1. Shortest paths and minimum spanning trees are measured in total weight rather than number of edges.
Related terms
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
- minimum spanning tree — The spanning tree of a weighted, connected graph whose edges have the smallest possible total weight.
- adjacency list — A graph representation that stores, for each vertex, a list of its neighbours, typically as a dict of lists in Python.
Taught in
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers