Weighted vs Unweighted Graph

Graphs can be unweighted (all edges cost the same) or weighted (each edge carries a cost, distance, or capacity). This distinction determines which shortest‑path or traversal algorithms are appropriate.

Unweighted Graphs

In an unweighted graph:

  • All edges are treated the same; you typically care about the number of steps (edges) rather than numeric costs.
  • Edge weight can be thought of as implicitly 1.

Shortest path problems in unweighted graphs:

  • “Minimum number of edges from A to B.”
  • “Minimum number of moves to reach a target state.”

Solution:

  • Use BFS to find shortest paths in O(n + m) time.

Weighted Graphs

In a weighted graph:

  • Each edge (u, v) has an associated weight w(u, v) (cost, distance, time, risk, etc.).
  • You care about the sum of weights along a path, not just edge count.

Examples:

  • Road networks with distances or travel times.
  • Network latency between servers.
  • Weighted dependencies or penalties in optimization problems.

Shortest path algorithms:

  • Non‑negative weights:
    • Dijkstra’s algorithm (using a min‑heap).
  • Can have negative edges but no negative cycles:
    • Bellman–Ford or SPFA.
  • Negative cycles:
    • No well‑defined shortest path; you typically detect cycles instead.

Representation Differences

In code, edge weights are usually stored as:

  • Extra field per edge in an adjacency list:
    • adj[u] contains pairs (v, weight).
  • Entries in an adjacency matrix:
    • matrix[u][v] stores weight, or ∞ / special value for “no edge”.

Example (adjacency list, weighted directed graph):

Java
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
// add edge u -> v with weight w
adj.get(u).add(new int[]{v, w});

Choosing the Right Algorithm

  • If the graph is unweighted (or all weights are equal), use BFS.
  • If edges have non‑negative weights, use Dijkstra.
  • If edges may be negative (but no negative cycles), use Bellman–Ford.

Picking the wrong algorithm (e.g. BFS on a weighted graph) can yield incorrect results, even if the code compiles and runs.