- A weighted graph is a graph
whose edges have
weights
- The weight of an edge is
typically the
cost/limitation of that
edge
- Common costs:
- distance between
2 vertices
- capacity of the link (edge) between 2 vertices
- distance between
2 vertices
- Example:
- Adjacency list: add a cost field
to the list element
- Example:
- Graph:
- Representation:
- Graph:
- Java classes:
/* ======================================= List element that represents an edge ======================================= */ class Edge { int NodeID; // The neighbor node double Weight; // Weight of edge Node next; // Next Edge in the list } /* ======================================= The nodes ======================================= */ Edge[] node; // Node[i] contains a list of neighbor for i
- Storing weights:
- The weights of the edges are represented as a floating-point value in the matrix
- Example:
- Graph:
- Representation:
0 1 2 3 4 5 6 7 8 +- -+ | * 3 * 2 * * * * 4 | // 0 | 3 * * * * * * 4 * | // 1 | * * * 6 * 1 * 2 * | // 2 | 2 * 6 * 1 * * * * | // 3 M = | * * * 1 * * * * 8 | // 4 | * * 1 * * * 8 * * | // 5 | * * * * * 8 * * * | // 6 | * 4 2 * * * * * * | // 7 | 4 * * * 8 * * * * | // 8 +- -+ * = a very large value (infinite)
- Graph:
- Java variables:
/* ======================================= The edges ======================================= */ double[][] M; // M[i][j] > 0 <==> weight of edge (i,j)
- Definition:
- Length of a path = the sum of the weights of the edges in the path
- Example:
- A path from 0 to 2:
length of path = 3 + 4 + 2 = 9
- A path from 0 to 2:
- Definition:
- Shortest path = the path that has the shortest length
- Example:
- The shortest path from 0 to 2:
length of the shortest path = 2 + 6 = 8
- The shortest path from 0 to 2: