**News Alert:**Experts Exchange Confirmed as Safe in Cloudbleed Leak Read More

3 Comments

I'll post it if you swear this is not a homework ;)

-julio

/* given a set of n vertices, a source vertex v and an nx n cost array c, this algorithm returns the cost fo the cheapest path from v to every other vertex. The vertices are index from 1 to n: T[i] is true iff the vertex i is included in T */

SingleSource( n,v,c)

for( i=1 to n) {

cost[i] = c[v,i]; /* initialise cost matrix */

T[v] = false; /* T is initially empty */

}

T[v] = true; /* include source vertex in T */

newest = v; /* newest node used to update cost */

for( i = 2 to n) { /* choose the ith vertex of T and see */

leastcost = INFINITY /* if inclusion of the latest */

for( j=1 to n) { /* node in T allows cheaper access */

if( !T[j] ) { /* to any node not in T */

if( cost[newest] + c[newest,j] < cost[j]) {

cost[j] = cost[newest] + c[newest,j];

} /* endif */ /* kind of useless if i = 2 */

if( cost[j] < leastcost) { /*and keep track of */

cheapest = j; /* the vertex not in T */

leascost = cost[j]; /* with the lowest access */

} /* endif */

} /* endif *

T[cheapest] = true; /* include this vertex in T */

newest = cheapest /* and record it as the */

} /* end for */ /* newest vertex */

} /* end for */

return (cost);

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

How do I avoid pointer to integer casting errors in C programming? | 4 | 226 | |

Coverting 24 hour time to 12 hour in C++ | 15 | 173 | |

Super Scope, DHCP | 5 | 78 | |

What is sub-make ? | 2 | 61 |

Join the community of 500,000 technology professionals and ask your questions.