Weighted Adjacency Matrix for Directed Graphs

Space: O(n²)Weight Query: O(1)Weighted Matrix

⚖️Understanding Weighted Adjacency Matrices

A weighted adjacency matrix is a square matrix used to represent a weighted directed graph. For a graph with n vertices, the adjacency matrix is an n×n matrixwhere each cell [i][j] contains the weight of the edge from vertex i to vertex j, or 0 if no edge exists.

Unlike unweighted graphs that store only 0s and 1s, weighted matrices store actual edge weights, making them ideal for representing distances, costs, capacities, or any numerical relationship between vertices.

matrix[i][j] = weight if edge exists from vertex i to vertex j, 0 otherwise

💻Implementation

// Weighted Adjacency Matrix for Directed Graph
class WeightedDirectedGraph {
  constructor(numVertices) {
    this.numVertices = numVertices;
    this.adjMatrix = Array(numVertices).fill(null)
      .map(() => Array(numVertices).fill(0));
  }
  
  // Add a weighted edge from source to destination
  addEdge(src, dest, weight) {
    if (src >= 0 && src < this.numVertices && 
        dest >= 0 && dest < this.numVertices && weight > 0) {
      this.adjMatrix[src][dest] = weight;
    }
  }
  
  // Remove an edge from source to destination
  removeEdge(src, dest) {
    if (src >= 0 && src < this.numVertices && 
        dest >= 0 && dest < this.numVertices) {
      this.adjMatrix[src][dest] = 0;
    }
  }
  
  // Get weight of edge between vertices
  getEdgeWeight(src, dest) {
    if (src >= 0 && src < this.numVertices && 
        dest >= 0 && dest < this.numVertices) {
      return this.adjMatrix[src][dest];
    }
    return 0;
  }
  
  // Check if edge exists
  hasEdge(src, dest) {
    return this.getEdgeWeight(src, dest) > 0;
  }
  
  // Get all neighbors with their weights
  getNeighborsWithWeights(vertex) {
    let neighbors = [];
    for (let i = 0; i < this.numVertices; i++) {
      if (this.adjMatrix[vertex][i] > 0) {
        neighbors.push({vertex: i, weight: this.adjMatrix[vertex][i]});
      }
    }
    return neighbors;
  }
  
  // Get total weight of all outgoing edges from a vertex
  getVertexOutWeight(vertex) {
    let totalWeight = 0;
    for (let i = 0; i < this.numVertices; i++) {
      totalWeight += this.adjMatrix[vertex][i];
    }
    return totalWeight;
  }
  
  // Create from weighted edge list
  static fromWeightedEdgeList(numVertices, edges) {
    let graph = new WeightedDirectedGraph(numVertices);
    edges.forEach(([src, dest, weight]) => {
      graph.addEdge(src, dest, weight);
    });
    return graph;
  }
  
  // Display weighted matrix
  printMatrix() {
    console.log("Weighted Adjacency Matrix:");
    for (let i = 0; i < this.numVertices; i++) {
      console.log(this.adjMatrix[i].join("\t"));
    }
  }
}

// Example usage
let graph = new WeightedDirectedGraph(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 4, 20);
graph.addEdge(3, 4, 8);
graph.printMatrix();

🔍Properties & Complexity

Time Complexity

• Weight lookup: O(1)
• Add weighted edge: O(1)
• Remove edge: O(1)
• Get neighbors with weights: O(n)

Space & Properties

• Space: O(n²) always
• Memory: Fixed regardless of edge count
• Representation: Dense storage
• Matrix ops: Easy to perform

✅ Best Use Cases

• Weighted graphs: Roads with distances, network costs, capacities
• Fast weight queries: Frequent "what's the weight?" checks
• Shortest path algorithms: Dijkstra's, Floyd-Warshall implementations
• Dense weighted graphs: When most vertex pairs have weighted edges
• Flow networks: Max flow, min cost flow problems

⚠️ Limitations

• Space inefficient: Wastes memory for sparse graphs
• Fixed size: Difficult to add/remove vertices
• Large graphs: O(n²) space becomes prohibitive
• Iteration: O(n) to find all neighbors
• Cache performance: Poor for very large matrices