blocks|key|110707|text|这是一个常见的graph+theory+problem+algorithm|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|110708|110709|在图论中，最短路径问题是指在图的两个顶点(或节点)之间找到一条路径，使其构成边的权重之和最小。|blockquote|110710|110711|在道路地图上寻找两个交叉口之间的最短路径(图的顶点对应于交叉口，边对应于路段，每个路段的长度加权)的问题可以用图中最短路径问题的一个特殊情况来建模。|110712|110713|目前已经存在该算法的lot+of+implementations。更简单的实现是性能最差情况下为O(%7CE%7C%2B%7CV%7Clog%7CV%7C)的Dijkstra's+algorithm，其中|style|CODE|110714|110715|%7CV%7C是the+number+of+nodes|unordered-list-item|BOLD|110716|%7CE%7C是|110717|的边数|110718|算法工作的说明|110719|​|110720|📷|atomic|110721|110722|Dijkstra最短路径算法的定义|110723|110724|initial+starting.|110725|distance+-我们是节点Y的starting.|110726|distance的节点-是从初始节点到Y.|110727|的距离|110728|算法将分配一些初始距离值，并尝试逐步改善它们：|110729|110730|为每个节点分配一个暂定距离值:对于初始节点，将其设置为0，对于所有其他节点，将其设置为∞。|ordered-list-item|110731|将初始节点设置为当前。将所有其他节点标记为未访问的。创建一组所有未访问的节点，称为当前节点的未访问，考虑其所有未访问的邻居并计算它们的暂定距离。将新计算的暂定距离与当前指定的值进行比较，并指定较小的值。|110732|当我们考虑完当前节点的所有邻居后，将当前节点标记为已访问，并将其从|110733|集合中删除。该算法让finished.|110734|Otherwise，选择标有最小试探性距离的节点，将其设置为新的“当前节点”，然后返回步骤3。|110735|110736|你可以在github仓库mburst/dijkstras-algorithm上找到更多关于Dijkstra算法的实现。|110737|例如，这里是JavaScript+implementation|110738|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Shortest_path_problem|1|https://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms|2|https://en.wikipedia.org/wiki/Dijkstra%2527s_algorithm|3|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/498a1bbe852fb45e7cb750dd3c9014e8.gif|imageAlt|4|https://github.com/mburst/dijkstras-algorithm|5|https://github.com/mburst/dijkstras-algorithm/blob/master/dijkstras.js^0|7|U|0|0|0|0|0|0|0|1C|G|A|M|1|1T|K|2|0|0|0|3|0|0|3|0|0|0|0|0|1|3|0|0|0|0|0|H|0|0|Q|0|0|L|0|0|3|0|0|N|0|0|0|19|0|0|P|W|4|1A|3|1J|4|0|0|0|I|0|M|P|0|0|0|1N|C|Q|4|0|0|V|6|P|5|0^^$0|@$1|2|3|4|5|6|7|2M|8|@]|9|@$A|2N|B|2O|1|2P]]|C|$]]|$1|D|3|-4|5|6|7|2Q|8|@]|9|@]|C|$]]|$1|E|3|F|5|G|7|2R|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|2S|8|@]|9|@]|C|$]]|$1|I|3|J|5|6|7|2T|8|@]|9|@]|C|$]]|$1|K|3|-4|5|6|7|2U|8|@]|9|@]|C|$]]|$1|L|3|M|5|6|7|2V|8|@$A|2W|B|2X|N|O]]|9|@$A|2Y|B|2Z|1|30]|$A|31|B|32|1|33]]|C|$]]|$1|P|3|-4|5|6|7|34|8|@]|9|@]|C|$]]|$1|Q|3|R|5|S|7|35|8|@$A|36|B|37|N|T]]|9|@]|C|$]]|$1|U|3|V|5|S|7|38|8|@$A|39|B|3A|N|T]]|9|@]|C|$]]|$1|W|3|X|5|6|7|3B|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|6|7|3C|8|@]|9|@]|C|$]]|$1|10|3|11|5|6|7|3D|8|@]|9|@]|C|$]]|$1|12|3|13|5|14|7|3E|8|@]|9|@$A|3F|B|3G|1|3H]]|C|$]]|$1|15|3|11|5|6|7|3I|8|@]|9|@]|C|$]]|$1|16|3|17|5|6|7|3J|8|@]|9|@]|C|$]]|$1|18|3|-4|5|6|7|3K|8|@]|9|@]|C|$]]|$1|19|3|1A|5|S|7|3L|8|@$A|3M|B|3N|N|T]]|9|@]|C|$]]|$1|1B|3|1C|5|S|7|3O|8|@$A|3P|B|3Q|N|T]]|9|@]|C|$]]|$1|1D|3|1E|5|S|7|3R|8|@$A|3S|B|3T|N|T]]|9|@]|C|$]]|$1|1F|3|1G|5|6|7|3U|8|@$A|3V|B|3W|N|T]]|9|@]|C|$]]|$1|1H|3|1I|5|6|7|3X|8|@$A|3Y|B|3Z|N|T]]|9|@]|C|$]]|$1|1J|3|-4|5|6|7|40|8|@]|9|@]|C|$]]|$1|1K|3|1L|5|1M|7|41|8|@$A|42|B|43|N|T]]|9|@]|C|$]]|$1|1N|3|1O|5|1M|7|44|8|@$A|45|B|46|N|T]|$A|47|B|48|N|T]|$A|49|B|4A|N|T]|$A|4B|B|4C|N|T]]|9|@]|C|$]]|$1|1P|3|1Q|5|1M|7|4D|8|@]|9|@]|C|$]]|$1|1R|3|1S|5|1M|7|4E|8|@$A|4F|B|4G|N|T]]|9|@]|C|$]]|$1|1T|3|1U|5|1M|7|4H|8|@$A|4I|B|4J|N|T]]|9|@]|C|$]]|$1|1V|3|-4|5|6|7|4K|8|@]|9|@]|C|$]]|$1|1W|3|1X|5|6|7|4L|8|@$A|4M|B|4N|N|T]]|9|@$A|4O|B|4P|1|4Q]]|C|$]]|$1|1Y|3|1Z|5|6|7|4R|8|@$A|4S|B|4T|N|T]]|9|@$A|4U|B|4V|1|4W]]|C|$]]|$1|20|3|-4|5|6|7|4X|8|@]|9|@]|C|$]]]|21|$22|$5|23|24|25|C|$26|27]]|28|$5|23|24|25|C|$26|29]]|2A|$5|23|24|25|C|$26|2B]]|2C|$5|2D|24|2E|C|$2F|2G|2H|-4]]|2I|$5|23|24|25|C|$26|2J]]|2K|$5|23|24|25|C|$26|2L]]]]

This is a common <a href="https://en.wikipedia.org/wiki/Shortest_path_problem" rel="nofollow noreferrer">graph theory problem algorithm</a>

<blockquote>
 In graph theory, the shortest path problem is the problem of finding a
 path between two vertices (or nodes) in a graph such that the sum of
 the weights of its constituent edges is minimized.
 
 The problem of finding the shortest path between two intersections on
 a road map (the graph's vertices correspond to intersections and the
 edges correspond to road segments, each weighted by the length of its
 road segment) may be modeled by a special case of the shortest path
 problem in graphs.
</blockquote>

For now exists <a href="https://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms" rel="nofollow noreferrer">lot of implementations</a> of this algorithm. More simpler in implementation is a <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow noreferrer">Dijkstra's algorithm</a> with worst case performance as <code>O(|E|+|V|log|V|)</code> where

<ul>
<li>|V| is the number of nodes</li>
<li>|E| is the number of edges</li>
</ul>

<h2>Illustration of algorithm work</h2>

<a href="https://i.stack.imgur.com/9Ng5i.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9Ng5i.gif" alt="enter image description here"></a>

<h2>Definition of Dijkstra's Shortest Path Algorithm</h2>

<ul>
<li>initial node - the node at which we are starting.</li>
<li>distance of node Y - be the distance from the initial node to Y.</li>
</ul>

Algorithm will assign some initial distance values and will try to improve them step by step:

<ol>
<li>Assign to every node a tentative distance value: set it to 0 for our initial node and to ∞ for all other nodes.</li>
<li>Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.</li>
<li>For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.</li>
<li>When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.</li>
<li>If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is ∞ (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.</li>
<li>Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.</li>
</ol>

More implementations of Dijkstra algorithm you can find on github repository <a href="https://github.com/mburst/dijkstras-algorithm" rel="nofollow noreferrer">mburst/dijkstras-algorithm</a>.

For example here is <a href="https://github.com/mburst/dijkstras-algorithm/blob/master/dijkstras.js" rel="nofollow noreferrer">JavaScript implementation</a>

blocks|key|2868049|text|虽然dijkstra算法确实有效，但在你的例子中，这个图是一个未加权的图，所以一个简单的BFS应该就足够了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2868050|伪代码：|2868051|queue+=+[startingposition]
prev+=+[-1,+-1,+-1+...]+(array+of+n+elements,+all+-1)
while+(queue+not+empty)+
+++u+<-+pop(queue)
+++if+u+=+targetposition+then+DONE!+trace+the+*prev*+array+for+path
+++for+(v+in+every+unvisited+points+adjacent+to+u):
++++++prev[v]+=+u
++++++push+v+to+queue
+++end+for
end+while|code-block|syntax|javascript|2868052|prev数组还可用于检查是否访问了某个点。|2868053|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

While dijkstra algorithm definitely works, in your case the graph is an unweighted graph, so a simple BFS should suffice.

Pseudo code:

<pre><code>queue = [startingposition]
prev = [-1, -1, -1 ...] (array of n elements, all -1)
while (queue not empty) 
 u &lt;- pop(queue)
 if u = targetposition then DONE! trace the *prev* array for path
 for (v in every unvisited points adjacent to u):
 prev[v] = u
 push v to queue
 end for
end while
</code></pre>

The prev array can also be used to check if a point is visited.

blocks|key|110754|text|这里没有计算路径代价的条件，因为所有的路径代价都是1，所以你可以在这里运行普通的2DBFS算法，其复杂度将是O(V%2BE)(顶点和边)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|110755|这里每个节点都有两个属性。一个是行，另一个是列。所以你可以创建一对来表示单元格的值。以下是c%2B%2B代码和说明：|110756|#define+pii+pair<int,int>
int+fx[]={1,-1,0,0};+//Direction+array+for+moving+one+cell+to+another+cell+horizontaly
int+fy[]={0,0,1,-1};+//Direction+array+for+moving+one+cell+to+another+cell+verticaly
int+cell[100][100];+//cell[x][y]+if+this+cell+is+-1+then+it+is+block+(Here+it+is+your+brown+cell)
int+d[100][100],vis[100][100];+//d+means+destination+from+source.+
int+row,col;
void+bfs(int+sx,int+sy)+//Source+node+is+in+[sx][sy]+cell.
{
++++memset(vis,0,sizeof+vis);
++++vis[sx][sy]=1;
++++queue<pii>q;+//A+queue+containing+STL+pairs
++++q.push(pii(sx,sy));
++++while(!q.empty())
++++{+++++++
++++++++pii+top=q.front();+q.pop();
++++++++for(int+k=0;k<4;k%2B%2B)
++++++++{
++++++++++++int+tx=top.uu%2Bfx[k];
++++++++++++int+ty=top.vv%2Bfy[k];+//Neighbor+cell+[tx][ty]
++++++++++++if(tx>=0+and+tx<row+and+ty>=0+and+ty<col+and+cell[tx][ty]!=-1+and+vis[tx][ty]==0)+//Check+if+the+neighbor+is+valid+and+not+visited+before.
++++++++++++{+++++++++++++++
++++++++++++++++vis[tx][ty]=1;
++++++++++++++++d[tx][ty]=d[top.uu][top.vv]%2B1;+
++++++++++++++++q.push(pii(tx,ty));+//Pushing+a+new+pair+in+the+queue
++++++++++++}
++++++++}
++++}
}|code-block|syntax|javascript|110757|现在，您可以很容易地找到从dx单元格到您的最短路径。|110758|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Here there is no condition of calculating path cost because all path cost is 1. So you can run here normal 2D BFS algorithm and the complexity will be O(V+E)(vertex and edge).

Here every node has two property. One is row and other is column. So u can create a pair for denoting the value of a cell. Here is the c++ code and explanation:

<pre><code>#define pii pair&lt;int,int&gt;
int fx[]={1,-1,0,0}; //Direction array for moving one cell to another cell horizontaly
int fy[]={0,0,1,-1}; //Direction array for moving one cell to another cell verticaly
int cell[100][100]; //cell[x][y] if this cell is -1 then it is block (Here it is your brown cell)
int d[100][100],vis[100][100]; //d means destination from source. 
int row,col;
void bfs(int sx,int sy) //Source node is in [sx][sy] cell.
{
 memset(vis,0,sizeof vis);
 vis[sx][sy]=1;
 queue&lt;pii&gt;q; //A queue containing STL pairs
 q.push(pii(sx,sy));
 while(!q.empty())
 { 
 pii top=q.front(); q.pop();
 for(int k=0;k&lt;4;k++)
 {
 int tx=top.uu+fx[k];
 int ty=top.vv+fy[k]; //Neighbor cell [tx][ty]
 if(tx&gt;=0 and tx&lt;row and ty&gt;=0 and ty&lt;col and cell[tx][ty]!=-1 and vis[tx][ty]==0) //Check if the neighbor is valid and not visited before.
 { 
 vis[tx][ty]=1;
 d[tx][ty]=d[top.uu][top.vv]+1; 
 q.push(pii(tx,ty)); //Pushing a new pair in the queue
 }
 }
 }
}
</code></pre>

Now you can easily find your shortest path from the d[x][y] cell.

I have been working in the past weeks on a multiplayer HTML5 game, using <code>nodejs</code> and <code>websockets</code>.

I've been stuck in this problem for a little while.
Imagine that I have this tilesheet map implemented with an array (as shown below).

1 or brown tiles - there is an obstacle in the way and the player can not pass through it.

0 or green tiles - are free paths where the player is allowed to move. 

Access any tile on the map by calling:

<pre><code> array[x][y]
</code></pre>

<a href="https://i.stack.imgur.com/2tcTo.png" rel="noreferrer"><img src="https://i.stack.imgur.com/2tcTo.png" alt="tilesheet map - calculate the shortest route"></a>

I would like to create the fastest algorithm possible to find out the shortest route (if there is one) between two points of the map. How would you approach this problem? I know this is common problem. 

Example: 

Player at the position (1,7) fires a bullet with some AI that will toward the enemy player at the position (6,0). Bullet has to calculate the shortest route between the 2 players and if there aren´t any it would just explode against a wall.

Question: 

How to efficiently find the shortest route between two points?

Calculating the shortest route between two points

HTML5

在过去的几周里，我一直在使用nodejs和websockets开发一款多人HTML5游戏。我陷入这个问题已经有一段时间了。假设我用一个数组实现了这个图片表映射(如下所示)。1或brown tiles -路上有一个障碍物，玩家无法通过它。或green tiles -是允许玩家移动的自由路径。通过调用以下命令来访问地图上的...

问计算两点之间的最短路径
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算两点之间的最短路径EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算两点之间的最短路径
EN