algorithm - Distance between two nodes in weighted directed graph -

-

which algorithm optimized searching shortest distance between 2 nodes in positive weighted directed graph?

i know dijkstra option calculates src nodes. same floyd-warshall.

one additional issue. need distance node source , destination.

for example:

src - f, dest - f need calculate 2.45 in example, not 0 dijkstra get. can modify dijkstra? i've implemented 1 http://www.vogella.com/tutorials/javaalgorithmsdijkstra/article.html

graph http://www.math.cornell.edu/~numb3rs/blanco/net_dif.png

if algorithm find shortest path 1 vertex another, , b algorithm find shortest paths between vertex , other nodes, proven fact optimal complexity of not better optimal complexity of b. i.e. cannot compute path single vertex, have compute paths other nodes. in simple words, how can sure found shortest path if don't know paths other nodes?

however, though there exist no algorithm complexity better algorithm b, particular implementation of might made more optimized implementation of b, constant factor. in case of positive edges, can halt dijkstra algorithm when destination vertex relaxed. might still have process vertices in worst case.

this optimization wouldn't possible in case have negative edges, dijkstra algorithm cannot handle case either. need bellman–ford algorithm case.

floyd-warshall overkill here, don't need paths vertices others. dijkstra way go, think. if looking optimal complexity, can use heap-based implementation, or fibonacci heaps. complexities cases given in wiki page dijkstra algorithm. stated that:

this [dijkstra fibonacci heaps] asymptotically fastest known single-source shortest-path algorithm arbitrary directed graphs unbounded non-negative weights.

so shouldn't bother find asymptotically better algorithm.


Comments

Post a Comment

Popular posts from this blog

c++ - OpenCV Error: Assertion failed <scn == 3 ::scn == 4> in unknown function, -

-
i read alot other solution still confused should mine... #include <opencv2/objdetect/objdetect.hpp> #include <opencv2/highgui/highgui.hpp> #include <opencv2/imgproc/imgproc.hpp> #include <iostream> #include <stdio.h> using namespace std; using namespace cv; int main(int argc, const char** argv) { //create cascade classifier object used face detection cascadeclassifier face_cascade; //use haarcascade_frontalface_alt.xml library face_cascade.load("haarcascade_frontalface_alt.xml"); //setup video capture device , link first capture device videocapture capturedevice; capturedevice.open(0); //setup image files used in capture process mat captureframe; mat grayscaleframe; //create window present results namedwindow("outputcapture", 1); //create loop capture , find faces while (true) { //capture new image frame capturedevice >> captureframe; ...
Read more

php - render data via PDO::FETCH_FUNC vs loop -

-
i've been using 2 methods render data. the first one: function name($id,$name){ return '<div id="'.$id.'">'.$name.'</div>'; } echo implode($pdo->query("select id,name user")->fetchall(pdo::fetch_func,'name')); the second one: $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); foreach($users $user){ echo name($user->id,$user->name); } i don't understand how pdo::fetch_func works. tried figure out. however, not well-documented. could please explain fetch mode? , also, 1 performs better? thank you. both methods wrong , have learn how use templates , how separate business logic presentation logic. $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); tpl::assign('users', $users); is code business logic part. then in template <?php foreach $users $row): ?> <div id="<?=$...
Read more

The canvas has been tainted by cross-origin data in chrome only -

-
uncaught securityerror: failed execute 'getimagedata' on 'canvasrenderingcontext2d': canvas has been tainted cross-origin data i getting above error in chrome. code(following) works fine in mozilla. have not corss domain issue. why above error in chrome? var wheel_canvas, wheel_context, can_w, can_h, wheel_grd; var large_radius = 160; var small_radius = 120; var wheel_canvas = document.getelementbyid('wheel_canvas'); var wheel_context = wheel_canvas.getcontext('2d'); var can_w = $(wheel_canvas).width(); var can_h = $(wheel_canvas).height(); var centerx = can_w / 2, centery = can_h / 2; var wheel_grd = null; test('#ff0000'); function test(hex) { $('#clrpicker').css({'left': 210, 'top': 210 }); inverted = hexbw(hex); $('#color_val_show').val(hex); current_color_hex_val_selected = hex; $('#color_val_show').css({'color':inverted,'background':hex}); fillgradient...
Read more