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.


Comments

Post a Comment

Popular posts from this blog

javascript - Feed FileReader from server side files -

-
i´m starting customize/improve old audio editor project. can import audio tracks canvas via drag&drop computer. thing use audio tracks stored in server clicking on list of available tracks... instead of use <input type="file"> tags. how can read server side files filereader?ajax perhaps? in advance. this code file reader: player.prototype.loadfile = function(file, el) { //console.log(file); var reader = new filereader, filetypes = ['audio/mpeg', 'audio/mp3', 'audio/wave', 'audio/wav'], = this; if (filetypes.indexof(file.type) < 0) { throw('unsupported file format!'); } reader.onloadend = function(e) { if (e.target.readystate == filereader.done) { // done == 2 $('.progress').children().width('100%'); var onsuccess = function(audiobuffer) { $(el).trigger('audiee:fileloaded', [audiobuffer, file]); ...
Read more

How to Change swipe Tab Title color in java Android -

-
by default, view pager(swipe tabs) tab title color white want change orange. can 1 me please or share if have tutorial. thanks... use style in styles.xml , assign style tab layout. <style name="mymaterialtheme.tablayout" parent="widget.design.tablayout"> <item name="tabindicatorcolor">@android:color/white</item> <item name="tabindicatorheight">3dp</item> <item name="tabtextappearance">@style/mymaterialtheme.tablayout.textappearance</item> <item name="tabselectedtextcolor">@android:color/white</item> <item name="android:background">@color/colorprimary</item> </style> <style name="mymaterialtheme.tablayout.textappearance" parent="textappearance.design.tab"> <item name="android:textsize">14sp</item> <item name="android:textcolor">@color/tab_text_inactive</item> ...
Read more

Using globs in Perl replace one liner in TCL script -

-
i want run 1 perl 1 liner in tcl script below: exec perl -i -pe {s/substring/replacing_string/g} testfile; this works fine. but, if want modify files below: exec perl -i -pe {s/substring/replacing_string/g} *; it gives me error message: can't open '*': no such file or directory. while executing exec perl -i -pe {s/substring/replacing_string/g} *; i tried bracing '*', did not solve problem. requesting help... assuming files a , b , , c present in current working directory, executing echo * in shell prints a b c . because shell command evaluator recognizes wildcard characters , splices in list of 0 or more file names wildcard expression found. tcl's command evaluator not recognize wildcard characters, passes them unsubstituted command invoked. if command can work wildcards so. exec command doesn't, means pass wildcard expression shell command named command string. testing this, get % exec echo * * because asked shell exe...
Read more