A graph whose edge have a ”weight” or ”cost”. The weight of an edge can represent distance, time, or anything that models the “connection” between the pair of nodes it connects.