c - Shortest path with dynamic programming -

i don't want answer problem, need nudge in right direction.

given undirected graph g having n (1<n<=1000) vertices , positive weights. find shortest path vertex 1 vertex n, or state such path doesn’t exist.

hint: @ each step, among vertices weren’t yet checked , path vertex 1 found, take 1 has shortest path, vertex 1 it, yet found.

first have define state. said:

the state solution vertex i, i <= n. smaller state solution j, j<i. find state i, need find smaller states j (j<i). having found shortest path i, can find next state - solution i+1.

i took different problem , replaced variable names , words because sounded applicable one.

i have write program solution, don't know how start. here questions:

1. is definition of state correct?

2. moreover, since undirected graph, , each vertex bidirectional, weights passed in multidimensional array (i.e int w[n][2]) w[n][0] weight of 1 vertex , w[n][1] weight of other?

3. how represent shortest path? number of paths taken, sum of weights of paths taken, or array of weights of paths taken?

have considered all-pairs shortest paths algorithms? floyd-warshall algorithm example sounds possible solution problem.

floyd-warshall algorithm dynamic programing algorithm. floyd-warshal algorithm supports directed graphs hence undirected.

floyd-warshall has time complexity of Θ(|v|^3) , space complexity of Θ(|v|^2)

wikipedia link https://en.wikipedia.org/wiki/floyd%e2%80%93warshall_algorithm

c implementation http://www.c-program-example.com/2011/10/c-program-to-implement-warshalls.html

finding path can left exercise link has example of how done need translate c. can find under matrix of predecessors http://www.programming-algorithms.net/article/45708/floyd-warshall-algorithm

this seems nice visual representation of algorithm https://www.cs.usfca.edu/~galles/visualization/floyd.html

another approach bellman ford algorithm. not pairs shortest path, instead computes shortest path single point other vertices.

bellman-ford algorithm dynamic programing algorithm. bellman-ford algorithm supports weighted directed graphs hence undirected.

bellman-ford has time complexity of Θ(|v||e|) , space complexity of Θ(|v|)

wikipedia link https://en.wikipedia.org/wiki/bellman%e2%80%93ford_algorithm

c implementation http://www.cs.dartmouth.edu/~cs57/project/bellman-ford.c

in case (assuming space complexity not issue here) choosing between 2 depend on number of vertices compared number of edges. if |e| greater (|v|^2) should go warshall-floyd otherwise if (|v|^2) greater |e| should go bellman-ford.