#define NOTHING -1
#define H 10
#define V 10
int cost_matrix[H][V] =
P0 P1 P2 P3 P4 P5 P6 P7 P8 P9
P0 { {-1, 5, 5, 6, -1, 7, -1, -1, -1, -1},
P1 { 5, -1, -1, -1, -1, -1, -1, 4, -1, -1},
P2 { 5, -1, -1, -1, 6, -1, -1, -1, -1, -1},
P3 { 6, -1, -1, -1, 5, -1, -1, -1, 2, -1},
P4 {-1, -1, 6, 5, -1, -1, 4, -1, -1, 5},
P5 { 7, -1, -1, -1, -1, -1, 3, -1, -1, -1},
P6 {-1, -1, -1, -1, 4, 3, -1, -1, -1, -1},
P7 {-1, 4, -1, -1, -1, -1, -1, -1, -1, 2},
P8 {-1, -1, -1, 2, -1, -1, -1, -1, -1, 1},
P9 {-1, -1, -1, -1, 5, -1, -1, 2, 1, -1}};
struct node {
int number;
int cost;
struct node *parent;
struct node *next;
};
struct node *CLOSED, *n, *newnode, *OPEN;
// Initialize this problem.
OPEN = NULL;
CLOSED = NULL;
n = create_new_node(0, 0);
add_to_list(&OPEN, &n);
while(searching){
if(is_empty(OPEN))
no_solution_exists(&searching);
else{ /* OPEN list is not empty */
// Take the node on OPEN list that has the lowest
// cost and put it on the CLOSED list.
n = remove_from_list(&OPEN, goal);
add_to_list(&CLOSED, &n);
if(is_a_goal_node(n, goal))
solution_found(n, &searching);
else{ /* else not done yet */
// Expand node n using the cost matrix.
for(i=0; i<H; i++){
cost = cost_matrix[n->number][i];
if(cost != NOTHING){
// First expand n if it is the start node.
if(n->parent == NULL){
newnode = create_new_node(i, cost+n->cost);
newnode->parent = n;
add_to_list(&OPEN, &newnode);
} /* ends if start node */
// Expand nodes that are not the start node.
// Do not expand the parent node of node n.
else{ /* not start node */
if((n->parent)-> number != i){
newnode = create_new_node(i, cost+n->cost);
newnode->parent = n;
add_to_list(&OPEN, &newnode);
} /* ends if */
} /* ends else not start node */
} /* ends if != NOTHING */
} /* ends expanding loop over i */
} /* ends else not done yet */
} /* ends else OPEN is not empty */
} /* ends while searching */