Spojení mezi dvěma vrcholy grafu. v ohodnocený graf, každý okraj má číslo, zvané "váhu". V orientovaný graf okraj jde z jednoho vrcholu, zdroj, do druhého, cíl a proto je spojení pouze jedním směrem.