Section 5.3: Matrix Representation of Graphs

SECTION 5.3 Matrix Representation of Graphs

New Terminology

A digraph is simply a directed graph, as was first introduced in Section 5.1. A digraph allows travel between nodes only in the direction indicated by the arrowed path lines, which are called directed edges.

A weighted graph is a digraph which has values attached to the directed edges. These values represent the cost of travelling from one node to the next. The cost can be measured in many terms, depending upon the application. For instance, the 3 digraphs below all represent the same thing; a graph of airport terminals and flight lines between those terminals. The only difference is the meaning of the weights of the edges: Graph A represents the flight distance between terminals; graph B represents the average flight time in minutes; and graph C represents the dollar cost of a plane ticket between the hubs. Looking at graphs A and B, you can see that the relative cost of a direct flight from hub 1 to 3 is cheaper in terms of time and miles than the more roundabout route of travel from hub 1 to 2 to 3. However, in graph C, the ticket costs of a roundabout route is cheaper than the direct flight.

A weighted adjacency matrix is a matrix representation of a weighted graph. (For a review of matrix algebra, go back to Section 2.4.)

Let v_i and v_j be numbered vertices for 1 < i, j < 4. Let w_ij be the weight of a directed edge if there exists an edge e = (v_i, v_j), and assume that all edge weights are positive; w_ij > 0. Let M[i, j] be an adjacency matrix where M[i, j] = w[i,j] if there exists an edge e = (v_i, v_j). For each vertex i in the graph, M[i, i] = 0, and where no path exists, M[i, j] = . Matrix M for graph C is shown below.

Matrix M

_	1	2	3	4
1	0	100	200	50
2		0	75
3			0
4		45	85	0

Warshall's Algorithm

In it's simplest form, Warshall's Algorithm is used to compute the existence of paths within a digraph using Boolean operators and matrices. Begin by creating an adjacency matrix A for Graph E as before, with one notable difference - instead of using weights (and you will have noticed by now that none are assigned to digraph E), we will use Boolean operators. That is to say, if there is a path, enter a 1 in matrix A, and enter 0 if no path exists.

A	1	2	3	4	5
1	0	0	1	0	0
2	0	0	0	1	0
3	0	1	0	0	1
4	0	1	0	0	0
5	1	0	0	0	0

This matrix tells us whether or not there is a path p of length 1 between two adjacent nodes. Building upon matrix A, we will create a new matrix A¹, for which we will choose one vertex to act as a pivot -- an intermediate point between 2 other vertices. Initially, we will chose vertex 1 as our pivot for A¹. The value we are seeking is that of p⁽¹⁾_i
j . For vertices v_i and v_j, p⁽¹⁾_{i j} is one of the following:

1, if there exists an edge between vertices v_i and v_j, or if there is a path of length > 2 from v_i to v₁ and from v₁ to v_j; else

0, if there is no path.

First, realize that all paths of length 1 between vertices v_i and v_j are already established. We are searching now for any paths of length 2 which use vertex 1 as a pivot point. The only way vertex 1 can be a pivot is if a path already lies between some vertex v_i and 1, and between 1 and some vertex v_j.

MATRIX A¹

Begin by scanning column 1 of matrix A; the only v_i which connects to v₁ is vertex 5.

Now scan row 1; the only path from v₁ to v_j is to vertex 3.

Since we have established that a path of length 2 lies between v₅ and v₃ , we update matrix A¹ accordingly.

MATRIX A²

Next create matrix A², using vertex 2 as the pivot point.

Begin by scanning column 2 of matrix A; the v_i which connect to v₂ are vertices 3 and 4.

Now scan row 2; only 1 path from v₂ exists to v_j = vertex 4.

We have now established paths between the following vertices:

v₃ to v₄ and v₄ to v₄.

Newly added paths have been highlighted in gray. Notice that each new path created is being built upon previously existing paths.

MATRIX A³

Matrix A³ will use vertex 3 as the pivot point.

As before, scan column 3 to see which vertices v_i connect to v₃ . In this case, vertices 1 and 5 have a path to 3.

Now, scanning row 3, v₃ connects to vertices 2, 4, 5. We have now established paths between the following:

v₁ to v₂	and	v₅ to v₂
v₁ to v₄		v₅ to v₄
v₁ to v₅		v₅ to v₅

Notice now that some paths have exceeded length 2. This is because the newly established paths are not using just 3 as a pivot point, but also the previous pivots points. For instance, vertex 5 has a path to 4 by travelling along the path of 51324, shown below.

If you haven't guessed by now, we will be creating 2 more adjacency matrices, A⁴ and A⁵. Generally speaking, if a graph has n vertices, it will require n matrices to produce Aⁿ = Pⁿ, where Pⁿ is the path matrix. To produce A⁴ and A⁵, proceed as before.

MATRICES A⁴and A⁵

For A⁴, first scan column 4. At this point, all vertices now have a path to vertex 4.

Scanning row 4, we see that 4 has a path only to vertex 2, indicating that all vertices have a path to 2. However, the only vertex which doesn't already have a path to vertex 2 is 2 itself, so we update the matrix accordingly.

Completing this process, scan column 5 to see that vertices 1, 3 and 5 all have paths to vertex 5. Scanning row 5 indicates that 5 has a path to all other vertices. Consequently, we add 1's to rows 1, 3 and 5 to reflect that vertices 1, 3 and 5 have paths to all other vertices.

This completes the path matrix for Graph E.

A¹	1	2	3	4	5
1	0	0	1	0	0
2	0	0	0	1	0
3	0	1	0	0	1
4	0	1	0	0	0
5	1	0	1	0	0

A²	1	2	3	4	5
1	0	0	1	0	0
2	0	0	0	1	0
3	0	1	0	1	1
4	0	1	0	1	0
5	1	0	1	0	0

A³	1	2	3	4	5
1	0	1	1	1	1
2	0	0	0	1	0
3	0	1	0	1	1
4	0	1	0	1	0
5	1	1	1	1	1

A⁴	1	2	3	4	5
1	0	1	1	1	1
2	0	1	0	1	0
3	0	1	0	1	1
4	0	1	0	1	0
5	1	1	1	1	1

A⁵	1	2	3	4	5
1	1	1	1	1	1
2	0	1	0	1	0
3	1	1	1	1	1
4	0	1	0	1	0
5	1	1	1	1	1

Warshall's Algorithm for computing a path matrix:

procedure Warshall (
A: BoolMatrix; var P: BoolMatrix; n: integer ); int i, j, k;		/Input, the adjacency matrix of a given graph/ /Output, the path matrix of the graph/ /Input, the size of the matrix (i.e., the number of vertices)/
begin
for i :=1 to n do for j := 1 to n do P[i, j] := A[i, j];		/Step 1: Copy adjacency matrix into path matrix/
for k := 1 to n do		/Step 2: Allow vertex k as a pivot point/
for i := 1 to n do		/Step 3: Process rows/
for j := 1 to n do		/Step 4: Process columns/
P[i, j] := P[i, j] or (P[i, k] and P[k, j])		/Step 5/
end;

Dijkstra's Algorithm

Suppose that we are given the following graph and are to find the shortest path between vertex 1 and all other vertices. We will begin by creating a set V which contains all vertices in graph D; V = {1, 2, 3, 4, 5, 6, 7}. Likewise, we can represent the shortest path between any 2 nodes as a set of vertices W. The approach we will take to solving this problem is to begin with W = {1}, and then we will progressively enlarge W one vertex at a time until W contains all vertices v in V. We will also create an array, ShortestPath[s], which will keep track of the minimum distance between vertex 1 and each vertex in W, and between vertex 1 and any vertex s V-W via a path p from the vertices in W. All vertices in path p will lie in W except for the last vertex s, which is in V-W.

At each step, the following will happen:

We will chose a vertex w to add to W from the set V-W (the difference of set V with respect to W) where there exists an edge e = (v_i, v_j), where vertex v_i W, and v_j V-W, and which has the minimum weight of all e leaving W.
We will update the array ShortestPath[s], so that at each step, the shortest path between 1 and all vertices will be recorded. The notation (s) represents the shortest distance between the origin (vertex 1) and vertex s.

To keep graph D available in a popup window, click here.
(Don't forget to close the window when you're done!)

Begin by letting W = {1}, V-W = {2, 3, 4, 5, 6, 7}, w = -- (since no vertex has been chosen to be added), and we create the ShortestPath[s] array (the green columns) as follows:

*Step*	W	V-W	w	(w)	(1)	(2)	(3)	(4)	(5)	(6)	(7)
1	{1}	{2, 3, 4, 5, 6, 7)	--	--	0	5	8		7	10

Notice that values are defined only for those vertices which can be reached directly from vertex 1 -- the only element currently in set W. Step 2 involves choosing a w, the vertex in V-W whose edge e = (1, w) is the minimum weight of all edges leaving set W. Looking at the array ShortestPath[s] in step 1 above, it can be seen that vertex 2 has the minimum distance from 1. So we choose w = 2 , and update W, V-W, and ShortestPath[s] accordingly.

*Step*	W	V-W	w	(w)	(1)	(2)	(3)	(4)	(5)	(6)	(7)
1	{1}	{2, 3, 4, 5, 6, 7)	--	--	0	5	8		7	10
2	{1, 2}	{3, 4, 5, 6, 7}	2	5	0	5	6		7	10

(w) has now been updated to 5, which was the minimum e available. Because vertex 2 has been added to W, set V-W has been shrunk by 1 element. Note that the minimum distance to vertex 3 equals the distance from 1 to 3 (not from 2 to 3!). Also note that the minimum distance to vertex 3 has decreased; by adding vertex 2 to W, a new path to 3 is available which costs less than the original path. Since vertices 1 and 5 are already in W, we mark them in yellow (so we won't make the mistake of choosing them again). Choosing the next smallest path from V-W, we let w = vertex 3 (highlighted in red).

*Step*	W	V-W	w	(w)	(1)	(2)	(3)	(4)	(5)	(6)	(7)
1	{1}	{2, 3, 4, 5, 6, 7)	--	--	0	5	8		7	10
2	{1, 2}	{3, 4, 5, 6, 7}	2	5	0	5	6		7	10
3	{1, 2, 3}	{4, 5, 6, 7}	3	6	0	5	6	12	7	10

Adding vertex 3 to set W has now made vertex 4 reachable, which is reflected in (4)'s change from to 12. Since vertex 5 now has the minimum distance of all vertices available in V-W from W, we choose it as w and add it to W in the next step. Proceeding with steps 4 through 7 will yield the following table.

*Step*	W	V-W	w	(w)	(1)	(2)	(3)	(4)	(5)	(6)	(7)
1	{1}	{2, 3, 4, 5, 6, 7)	--	--	0	5	8		7	10
2	{1, 2}	{3, 4, 5, 6, 7}	2	5	0	5	6		7	10
3	{1, 2, 3}	{4, 5, 6, 7}	3	6	0	5	6	12	7	10
4	{1, 2, 3, 5}	{4, 6, 7}	5	7	0	5	6	11	7	9	14
5	{1, 2, 3, 5, 6}	{4, 7}	6	9	0	5	6	11	7	9	13
6	{1, 2, 3, 4, 5, 6}	{7}	4	11	0	5	6	11	7	9	13
7	{1, 2, 3, 4, 5, 6, 7}	{ }	7	13	0	5	6	11	7	9	13

At each the end of each step, we have highlighted the path (in red) in V-W with the minimum distance from vertex 1, and added that vertex to W in the next step. To make choosing the next vertex easier, all vertices already in W are marked in yellow: at the end of the process, all vertices formerly in V-W are now elements of W. The end result is an array which gives the shortest path from 1 to all other vertices in graph D.

This is a specific example of choosing a shortest path. Dijkstra's Algorithm, named after it's discovered, Edsger W. Dijkstra, provides a general algorithm for finding shortest path as follows:

Let G = (V, E) be a weighted, directed graph.
Let T[i, j] give the weight on the edge from vertex i to vertex j, and assume the following:

T[i, j] > 0 (T[i, j] is non-negative);
T[i, i] = 0;
T[i, j] > 0 if there is an edge from vertex i to vertex j in edge set E; and
T[i, j] = if there is no edge from vertex i to vertex j in E;

void ShortestPath(void)
{

(Let MinDist be a variable which contains edge weights as values)
(and let Minimum(x,y) be a function which returns the lesser value of x and y.)

/*Let v₁ V be the vertex at which ShortestPath begins.*/
/*Initialize W and ShortDist[x] as follows:*/

W = {v₁};
ShortDist[v₁] = 0;
for (each x in V - {v₁}) ShortDist[x] = T[v₁][x];

/*Begin enlarging W 1 vertex at a time until W contains all vertices in V.*/

while (W != V) {

/*Find the vertex w V-W which has the shortest distance from v₁.*/

MinDist = ;

for (each w V-W) {
     if(ShortDist[v] < MinDist) {
          MinDist = ShortDist[v];
          w = v;
     }
}

/*Add w to W*/

W = W {w};

/*Update the ShortDist array.*/

for (each x V-W) {
ShortDist[x] =
Minimum(ShortDist[x], ShortDist[w] + T[w][x]);
}

}

Go to next section review
Go to Class Agenda