Graph/SingleSourceShortestPath/rawDense.cxx File Reference

optimized Dijkstra's implementation for dense graphs More...

#include <iostream>
#include "Graph.h"

Functions

void output (int n, int *const dist, int *const pred)
 Useful for debugging.
void singleSourceShortestDense (int n, int **const weight, int s, int *dist, int *pred)
 Interface to dense version of single source Shortest Path problem.


Detailed Description

optimized Dijkstra's implementation for dense graphs

Contains implementation of Dijkstra's Algorithm for solving Single Source Shortest Path problems as optimized for dense graphs. The input is a two-dimensional array rather than a graph structure.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void output ( int  n,
int *const   dist,
int *const   pred 
)

Useful for debugging.

void singleSourceShortestDense ( int  n,
int **const   weight,
int  s,
int *  dist,
int *  pred 
)

Interface to dense version of single source Shortest Path problem.

An edge weight of INF means no edge. Suitable for Dense Graphs Only.

Parameters:
n number of vertices in graph
weight two-dimensional array of edge weights (INF means no edge).
s the source vertex from which to compute all paths.
dist computed dist[] array to all other vertices.
pred computed pred[]array to contain back references for paths.

Algorithm Development Kit 1.0