We help IT Professionals succeed at work.

Dijkistra Shortest Path

on
Medium Priority
800 Views
Hi guys
Does anyone has the source for Dijkistra's 'Shortest Path' algorithm?
Comment
Watch Question

View Solution Only

Commented:
Finding the Shortest Path in a dense graph??

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

-julio

Commented:
Of course...
Commented:
From "design and analysis of algorithms" - Jeff Smith

/* 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 */
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 */
} /* 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);

Not the solution you were looking for? Getting a personalized solution is easy.

Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile