گراف وزن‌دار

• گرافی که راس‌های آن دارای وزن می‌باشند.
• گرافی که یال‌های آن دارای وزن می‌باشند.
• گرافی که هم راس و هم یال‌های آن دارای وزن می‌باشند.

وزن هر یال یک گراف موزون می‌تواند نشان دهنده یکی از موارد زیر باشد:

• هزینه یا مسافت: میزان هزینه یا مقدار مسافت برای جابه جایی از یک راس (مکان) به راس دیگر.
• ظرفیت: حد اکثر میزان چیزی که می‌تواند از یک راس (مکان) به راس دیگر منتقل شود.

کلاس مربوط به پیاده‌سازی یال‌ها:

  {
     int  NodeID;     // The neighbor node
     double Weight;   // وزن یال
     Node next;       // Link variable
  }

کلاس مربوط به پیاده‌سازی گراف

  {
      public Edge[] graph;    // Array of Edges
  }

• اگر بین دو راس i و j هیچ یالی نباشد، مقدار a[i][j] را برابر بینهایت قرار می‌دهیم.
• اگر بین دو راس i و j یالی باشد، مقدار a[i][j] را برابر ارزش آن یال قرار می‌دهیم.

کلاس مربوط به پیاده‌سازی گراف وزن‌دار با استفاده از ماتریس مجاورت

  {
     double[][] M;      // M[i][j] = weight of edge (i,j)
     ...
  }