גרף ממושקל

גרף ממושקל הינו גרף עבורו לכל קשת בגרף משויך "משקל". במלים אחרות, זהו גרף $G=\left(V,E\right)$ ופונקציית משקל $w:E\to \mathbb {R}$.

הצמדת משקל לקשתות בגרף מאפשרת למדל בעיות מעניינות רבות, ובכללן עץ פורס מינימלי, מציאת המרחק הקצר בגרף בין שני צמתים, מציאת כל המרחקים הקצרים ביותר בגרף, ועוד.