Search code examples
javaalgorithmdirected-graphadjacency-matrix

Algorithm to add weights in a directed graph (using adjacency matrix)

enter image description here

I apologize for the terrible graph I made in Paint.

Anyways, I'm having a hard time coming up with a single method on how to add weights in a graph.

Can anyone provide (using pseudocode) some insight on how to go about solving this problem. I've thought about using method overloading but it wouldn't work for every case. I am completely stuck. Keep in mind that I am using an adjacency matrix and not a list. Thank you!

Example:

Distance from Node 1 to Node 2 to Node 3 = 6

Distance from Node 1 to Node 2 to Node 3 to Node 4 = 8

Distance from Node 1 to Node 2 to Node 3 to Node 4 to Node 2 to Node 3 = 18

Solution

  • Let's take the adjacency matrix for this graph you've provided, it looks like this let INF be a nonexistant link.

       1   2   3   4
1 INF  3  INF  3 
2 INF INF  3  INF
3 INF INF INF  2
4 INF  7  INF INF

    This stores all the relevant information about the graph, and provides some extremely simple algorithms. To get the weight of a particular edge from node x to y, simply take AdjacencyMatrix[x][y]. Either it'll be a weight, or INF indicating no link exists.

    At that point, summing the weight of a path is extremely simple.