java - Finding the shortest path in a maze graph using adjacency matrix -


i have troubles solving of particular problem find shortest path in maze graph. probably, i'm stucked because of fact maze initialized 4 dimensional array adjacent = new boolean[height][width][height][width]; first , second pair of indices specify location in graph in row/column formation. graph looks this:

xxxxxxxxxxxxx ..........x.x x.xxx.xxx.x.x x.x.x...x.x.x x.x.xxx.xxx.x x...x.....x.. xxxxxxxxxxxxx

the arraylist must hold locations of vertices in path, in order start end inclusive.

i've written constructor , connection method; however, have trouble finding shortest path method. here example of how create maze graph:

final int edges[][] = {{1, 0, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 1},                  {1, 2, 1, 3}, {1, 3, 1, 4}, {1, 4, 1, 5}, {1, 5, 1, 6},                  {1, 5, 2, 5}, {1, 6, 1, 7}, {1, 7, 1, 8}, {1, 8, 1, 9},                  {1, 9, 2, 9}, {1, 11, 2, 11}, {2, 1, 3, 1}, {2, 5, 3, 5},                  {2, 9, 3, 9}, {2, 11, 3, 11}, {3, 1, 4, 1}, {3, 3, 4, 3},                  {3, 5, 3, 6}, {3, 6, 3, 7}, {3, 7, 4, 7}, {3, 11, 4, 11},                  {4, 1, 5, 1}, {4, 3, 5, 3}, {4, 7, 5, 7}, {4, 11, 5, 11},                  {5, 1, 5, 2}, {5, 2, 5, 3}, {5, 5, 5, 6}, {5, 6, 5, 7},                  {5, 7, 5, 8}, {5, 8, 5, 9}, {5, 11, 5, 12}};          mazegraph maze = new mazegraph(13, 7);           (int[] edge : edges)              maze.connect(new location(edge[0], edge[1]), new location(edge[2], edge[3]));

first of all, this

adjacent = new boolean[height][width][height][width];

contradicts this:

the first , second pair of indices specify location in graph in row/column formation.

it column/row, not row/column.

dijkstra's algorithm should implemented matrix. quote:

let node @ starting called initial node. let distance of node y distance initial node y. dijkstra's algorithm assign initial distance values , try improve them step step.

  1. assign every node tentative distance value: set 0 our initial node , infinity other nodes.

  2. set initial node current. mark other nodes unvisited. create set of unvisited nodes called unvisited set.

  3. for current node, consider of unvisited neighbors , calculate tentative distances. compare newly calculated tentative distance current assigned value , assign smaller one. example, if current node marked distance of 6, , edge connecting neighbor b has length 2, distance b (through a) 6 + 2 = 8. if b marked distance greater 8 change 8. otherwise, keep current value.

  4. when done considering of neighbors of current node, mark current node visited , remove unvisited set. visited node never checked again.

  5. if destination node has been marked visited (when planning route between 2 specific nodes) or if smallest tentative distance among nodes in unvisited set infinity (when planning complete traversal; occurs when there no connection between initial node , remaining unvisited nodes), stop. algorithm has finished.

  6. otherwise, select unvisited node marked smallest tentative distance, set new "current node", , go step 3.


Comments

Post a Comment

Popular posts from this blog

angularjs - ADAL JS Angular- WebAPI add a new role claim to the token -

i have created angular spa webapi backend using adal js authentication.as there no roles in ad, need manually add role claims in order give users access different api controllers. the roles stored in database. expecting inject claim through call webapi after authentication ad. webapi code might this. identity.addclaim(new claim("role", "user")); var ticket = new authenticationticket(identity, props); var accesstoken = startup.oauthbeareroptions.accesstokenformat.protect(ticket); is possible replace adal idtoken new token? is viable solution or there other better way handle this? as initial token generated azuread, possible edit token add new claim? appreciated. graph api supporting group claims. see here: http://justazure.com/azure-active-directory-part-4-group-claims/ if @ examples on page, users assigned groups , app can check group in claims. in current version of portal, need app manifest , modify it.
Read more

node.js - Using Node without global install -

i'm working on few node & electron (atom shell) projects , i'm curious how them work without user having install node globally. i've seen few applications including node directory in project contains node.exe binary. how go setting node project use binary? edit: thought should add, i've searched everywhere answer this, unrelated results.
Read more

php - CakePHP HttpSockets send array of paramms -

i problem when make request (i can request). $link = 'http://uri/path/?param1=1&sid=2&sid=3&sid=4' $http = $httpsocket = new httpsocket(); $res = $httpsocket->get($link); if check request pr($http); i see : [line] => /url/path/?param1=1&sid%5b0%5d=2&sid%5b1%5d=3&sid%5b2%5d=4 http/1.1 and i'm getting empty response because server doesn't know parameters sid%5b0%5d=2 when try send parameters array : $data = array('param1' => '1', 'sid' => array('2','3', '4')); i see same changes %5b0%5d - additional indexes. how fix it? unfortunately , can not change server side, if send request in browser, i'll normal response in json format. when make request, can parameters this: $param1 = $_get['param1']; $sid= $_get['sid']; tip: use diferente names parameters. have multiples sid. use sid1, sid2, sid3... update: can parameters this:...
Read more