Graphics Reference
In-Depth Information
Algorithm : The shortest path
struct vertex {
...
int distance;
} ;
void dijkstra shortest path ( set of struct vertex V , struct vertex v s , struct vertex v t )
/**********************************************************************
receives a set of vertices V , a source vertex v s and a target vertex v t ,
and computes the shortest path between v s and v t .
***********************************************************************/
{ set of struct vertex T ;
struct vertex u , v ;
V V \{ v s } ;
T ←{ v s } ;
v s .distance 0;
// initialization : the distance attribute of a vertex u V is equal to the edge weight w (( v s , u ))
// for all vertices incident from v s
for each u V
if (( v s , u ) E )
u .distance w (( v s , u ));
else u .distance ←+∞ ;
end
// main loop : at each iteration the vertex u in V with minimum distance attribute is moved to T .
// Distance attributes of the vertices in V are updated in the case that a path via u is shorter
// than the direct connection from v s
while ( v t T ) {
u u V , such that v V : u .distance v .distance”;
T T ∪{ u } ;
V V \{ u } ;
for each v “such that ( u , v ) E
if ( v .distance > w (( u , v )) + u .distance )
v .distance
w (( u , v )) + u .distance;
end
}
}
Figure 3.28 A pseudo-code description of Dijkstra's shortest path algorithm. This algorithm actually
only computes the length of the shortest path rather than the shortest path itself
vertices are sorted in ascendant order of distance attribute from the source vertex is reported
in Figure 3.29.
The Exercise 6 proposes the computation of the geodesic distance of the shortest path
between two vertices of a simple graph. In Exercise 7, the shortest path itself connecting two
vertices instead of merely its length is required to be computed.
 
Search WWH ::




Custom Search