graph theory - Shortest path with a fuel tank -


this homework question , i'd happy guidance.

let g=(v,e) undirected graph each vertex represents city, , edges have weights represents travel distances. of cities have gas stations in them. car starts vertex s gas tank sufficient travel length l. need find shortest path between s , t car won't run out of gas.

my main thought use floyd–warshall algorithm changes. when calculate shortestpath(i,j,0) assign w(i,j) if has gas station , l-w(i,j) > 0 , , infinity otherwise. however, next steps, don't know how add current fuel status calculations.

thanks.

make new weighted graph vertices: s, t , cities (c) gas station.

edges:

  • s-c, c c, if there shortest path between s , c has length <= l,
  • c1-c2, c1, c2 c, length c1-c2 <= l,
  • c-t, c c, length c-e <= l,
  • s-t, if length s-t <= l.

and edge weight set length v1-v2.

standard dijkstra on graph should return skeleton of shortest path looking on original graph.

it possible crate new graph 'iteratively' when dijkstra asks edges on boundary vertices. like, first create s-c , s-t edges (and vertices), , if there demand c1-c2 , c-t add these vertices , edges graph.


Comments

Post a Comment

Popular posts from this blog

python - How to create a legend for 3D bar in matplotlib? -

Image
given ax = plt.subplot() : ax.bar()[0] can passed plt.legend() . however, ax.bar3d() returns none . how create legend displayed bars? update: passing legend="stuff" ax.bar3d() , calling ax.legend() raises /usr/lib/python2.6/site-packages/matplotlib/axes.py:4368: userwarning: no labeled objects found. use label='...' kwarg on individual plots. warnings.warn("no labeled objects found. " you need use proxy artist legends not supported. this code: from mpl_toolkits.mplot3d import axes3d import matplotlib.pyplot plt import numpy np fig = plt.figure() ax = fig.add_subplot(111, projection='3d') x, y = np.random.rand(2, 100) * 4 hist, xedges, yedges = np.histogram2d(x, y, bins=4) elements = (len(xedges) - 1) * (len(yedges) - 1) xpos, ypos = np.meshgrid(xedges[:-1]+0.25, yedges[:-1]+0.25) xpos = xpos.flatten() ypos = ypos.flatten() zpos = np.zeros(elements) dx = 0.5 * np.ones_like(zpos) dy = dx.copy() dz = hist.flatten() ax...
Read more

java - Multi-Label Document Classification -

i have database in store data based upon following 3 fields: id, text, {labels}. note each text has been assigned more 1 label \ tag \ class. want build model (weka \ rapidminer \ mahout) able recommend \ classify bunch of labels \ tags \ classes given text. i have heard svm , naive bayes classifier, not sure whether support multi-label classification or not. guides me right direction more welcome! the basic multilabel classification method one-vs.-the-rest (ovr), called binary relevance (br). basic idea take off-the-shelf binary classifier, such naive bayes or svm, create k instances of solve k independent classification problems. in python-like pseudocode: for each class k: learner = svm(settings) # example labels = [class_of(x) == k x in samples] learner.learn(samples, labels) then @ prediction time, run each of binary classifiers on sample , collect labels predict positive. (both training , prediction can done in parallel, since problems assumed ...
Read more

php - Dynamic url re-writing using htaccess -

how can rewrite http://mydomain.com/test/master.php?catid=2&subcatid=8 http://mydomain.com/test/master.php/catname/subcat using .htaccess file. once rewritten, how can access these parameters in master.php? note: untested, let me know if doesn't work. rewriterule ^master.php/([a-za-z0-9_-]+)/([a-za-z0-9_-]+)$ /master.php?catid$1&subcatid=$2 [l]
Read more