digraph/directed_graph.c
/*
 * This buildTree funciton implements dijkstra's algorithm. It takes a DirectedGraph* struct
 * pointer and a void* origin vertex struct pointer, then creates a shotest path list by
 * assigning the parent data members for each vertex struct.
 * 
 */
This buildTree funciton implements dijkstra's algorithm. It takes a DirectedGraph* struct
pointer and a void* origin vertex struct pointer, then creates a shotest path list by
assigning the parent data members for each vertex struct.
This buildTree funciton implements dijkstra ' s algorithm . It takes a DirectedGraph * struct pointer and a void * origin vertex struct pointer then creates a shotest path list by assigning the parent data members for each vertex struct .
void buildTree(DirectedGraph* graph, void* origin)
{
	if(graph == NULL || origin == NULL)
		return;
	LinkedList* vList = get_vertices(graph);
	for(int i = 0; i < linked_list_size(vList); i++)
	{	
		Vertex* v = (Vertex*) linked_list_get(vList, i);
		set_vertex_distance(v, MAX);		
	}
	PriorityQueue* pq = pQueue_initialize(sizeof(Vertex), "Vertex", compareVertex);
	Vertex* start     = get_vertex(graph, origin);
	set_vertex_distance(start, 0);
	pQueue_enqueue(pq, start);
	while(pQueue_size(pq) > 0)
	{
		Vertex* v = (Vertex*) pQueue_dequeue(pq);
		if(been_visited(v))
		{
			continue;
		}
		set_visited(v, true);
		LinkedList* arcList = get_arc_list(v);
		for(int i = 0; i < linked_list_size(arcList); i++)
		{
			Arc* arc       = (Arc*) linked_list_get(arcList, i);
			Vertex* vtex   = arc->vertex;
			float distance = get_vertex_distance(v) + arc->weight; 
			if(get_vertex_distance(vtex) > distance)
			{
				set_vertex_distance(vtex, distance);
				set_vertex_parent(vtex, v);
				pQueue_enqueue(pq, vtex);
			}
		}	
	} 
}
void buildTree ( DirectedGraph * graph , void * origin ) { if ( graph == NULL || origin == NULL ) return ; LinkedList * vList = get_vertices ( graph ) ; for ( int i = 0 ; i < linked_list_size ( vList ) ; i ++ ) { Vertex * v = ( Vertex * ) linked_list_get ( vList , i ) ; set_vertex_distance ( v , MAX ) ; } PriorityQueue * pq = pQueue_initialize ( sizeof ( Vertex ) , " " , compareVertex ) ; Vertex * start = get_vertex ( graph , origin ) ; set_vertex_distance ( start , 0 ) ; pQueue_enqueue ( pq , start ) ; while ( pQueue_size ( pq ) > 0 ) { Vertex * v = ( Vertex * ) pQueue_dequeue ( pq ) ; if ( been_visited ( v ) ) { continue ; } set_visited ( v , true ) ; LinkedList * arcList = get_arc_list ( v ) ; for ( int i = 0 ; i < linked_list_size ( arcList ) ; i ++ ) { Arc * arc = ( Arc * ) linked_list_get ( arcList , i ) ; Vertex * vtex = arc -> vertex ; float distance = get_vertex_distance ( v ) + arc -> weight ; if ( get_vertex_distance ( vtex ) > distance ) { set_vertex_distance ( vtex , distance ) ; set_vertex_parent ( vtex , v ) ; pQueue_enqueue ( pq , vtex ) ; } } } }
This buildTree funciton implements dijkstra's algorithm.
This buildTree funciton implements dijkstra ' s algorithm .
// Get a linkedlist of the vertices in the graph. // For each vertex in the linkedlist. // get the vertex at the index and assign its distance data field to MAX. // Initializing the PriorityQueue struct with the compareVertex function as a parameter. // These two lines of code are for setting up dijkstra's algorithim (below). // While the priority queue contains elements. // Dequeue a vertex from the priority queue. // If this vertex has already been visited. // Force a new iteration of the while loop. // Set the vertex's visited data member to true. // Retrieve the list of arcs from this vertex. // For each arc from this vertex. // Get the arc at this index and the vertex. // Calculate a new distance. // If the vertex's diatance is greater than the calculated distance. /*
				 * Assign the calculated distance to the current vertex,
				 * assign the parent value for this vertex and the vertex 
				 * being dequeued, and enqueue this vertex. 
				 */