Page 277 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Therefore we shall have:

Table 13.3: Adjacency List Structure for Graph in Figure 13.11

v v m v
1 m 2 3
v v
2 m 3
v v
3 m 4
v m v
4 5
v m v v v
5 4 m 6 m 1
v
6

Note That adjacent vertices may appear in the adjacency list in arbitrary order. Also
an arrow from v to v in the list linked to v does not mean that V and V are adjacent.
2 3 1 2 3
The adjacency list representation is better for sparse graphs because the space required is
O(V + E), as contrasted with the O(V ) required by the adjacency matrix representation.
2
13.4 Shortest Path Algorithms

E.W. Dijkstra developed an algorithm to determine the shorted path between two nodes in a
graph. It is also possible to find the shortest paths from a given source node to all nodes in a

graph at the same time, hence this problem is sometimes called the single-source shortest paths
problem.
The shortest path problem may be expressed as follows:
Given a connected graph G = (V, E), with weighted edges and a fixed vertex s in V, to fi nd a

shortest path from s to each vertex v in V. The weights assigned to the edges may represent
distance, cost, effort or any other attribute that needs to be minimized in the graph.

A solution to this problem could be found by finding a spanning tree of the graph. The graph
representing all the paths from one vertex to all the others must be a spanning tree - it must
include all vertices. There will also be no cycles as a cycle would define more than one path from

the selected vertex to at least one other vertex.
The algorithm finds the routes, by cost precedence. Let’s assume that every cost is a positive

number. The algorithm is equally applicable to a graph, a digraph, or even to a mixed graph
with only some of its sides directed. If we consider a digraph, then every other case is fully
covered as well since a no directed side can be considered a 2 directed sides of equal cost for
every direction.
The algorithm is based on the fact that every minimal path containing more than one side is the
expansion of another minimal path containing a side less. This happens because all costs are
considered as positive numbers. In this way the fi rst route D(1) found by the algorithm will be
one arc route, that is from the starting point to one of the sides directly connected to this starting
point. The next route D(2) will be a one arc route itself, or a two arc route, but in this case will be
an expansion of D(1).

272 LOVELY PROFESSIONAL UNIVERSITY