pra*_*ran 12 c++ algorithm dijkstra
在过去的四天里,我试图了解dijkstra的算法.但我不能.我有一个点矢量.从那以后我创建了一个成本矩阵.但我不知道如何制作dijkstra的算法.来源有网,但我不是来自计算机科学背景,所以我无法理解它们.我正在尝试制作这样的功能
vector<int> dijkstra(costMatrix[][])
{
....
....
return vector<int>pathPointindex
}
main()
{
vector<Point> availablePoints;
costMatrix[][]=createCostMatrix();
vector<int> indexes=dijikstra(costMatrix)
for(int i=0;i<indexes.size();i++)
cout << "path points are " << availablePoints[indexes[i]] << endl;
}
如果有人,请您发布代码.我不懒.但是我的项目已经在一天前跨越了截止日期.现在我失去了理解逻辑的希望.现在我想要这个功能."有需要的人确实是天使".
编辑:特别感谢"Loki astari"的出色回答
Mar*_*ork 40
这是一种用于查找从A点到B点的最短路径的算法.
在计算术语中,我们简化了到由节点和弧组成的图的路径.每个节点表示一个中间点,而每个弧连接两个节点,并且具有(非负)权重,表示在两个节点之间遍历的成本.
要实现该算法,您需要两个列表:
算法:
working.addNode(Start, 0); // No cost to get to start.
for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
// If we have already processed this node ignore it.
if (finished.find(node))
{ continue;
}
// We have just removed a node from working.
// Because it is the top of the list it is guaranteed to be the shortest route to
// the node. If there is another route to the node it must go through one of the
// other nodes in the working list which means the cost to reach it will be higher
// (because working is sorted). Thus we have found the shortest route to the node.
// As we have found the shortest route to the node save it in finished.
finished.addNode(node,cost);
// For each arc leading from this node we need to find where we can get to.
foreach(arc in node.arcs())
{
dest = arc.dest();
if (NOT (finished.find(dest)))
{
// If the node is already in finished then we don't need to worry about it
// as that will be the shortest route other wise calculate the cost and add
// this new node to the working list.
destCost = arc.cost() + cost;
working.addNode(dest,destCost); // Note. Working is sorted list
}
}
}
所以如果你考虑这个算法.假设您从伦敦到曼彻斯特旅行.
finished = {} // empty.
working = { (London,0) }
使用以下Costs矩阵:
L S O B N M W
(L) ondon - 50 60 100 130 - -
(S) outhampton 50 - 70 - - - -
(O) xford 60 70 - 50 - 200 -
(B) irmingham 100 - 50 - - 80 110
(N) orwich 130 - - - - - -
(M) anchester - - 200 80 - - 80
Ne(W) castle - - - 110 - 80 -
现在,您将伦敦从工作列表中取出(因为它在头部)并将其放入完成的列表中.然后将所有直接连接到伦敦的城镇添加到工作清单中.
finished = { (London,0) }
working = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }
考虑工作区中的城镇是从伦敦扩展的泡沫的外缘.Dijkstra算法的工作是继续扩大泡沫,直到我们击中曼彻斯特(没有回顾我们已经采取的任何步骤).因此,泡沫总是向外扩展,我们总是扩大泡沫中最小的部分.
因此,下一步是采取列表的头部并重复.从南安普敦出发,只有两个目的地.回到伦敦(我们在完成的清单中将其丢弃)和牛津.到达牛津的费用是从南安普敦到牛津的费用是50+(因此请注意它在工作清单中两次,但不要担心我们以后会丢弃它作为最佳路线).
finished = { (London,0), (Southampton,50) }
working = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }
所以重复循环.名单的负责人是牛津大学.从牛津出发,我们可以去曼彻斯特(200),伯明翰(50)或回到伦敦(60)或南安普敦(请记住,我们需要增加牛津到上述每项费用的成本.请注意,从牛津我们可以有去了南安普敦但是我们已经找到了通往南安普敦的最短路线,所以不需要处理.这将给我们留下:
finished = { (London,0), (Southampton,50), (Oxford, 60) }
working = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}
请注意,我们现在在工作列表中有曼彻斯特(这是我们的目的地).但我们需要继续努力,因为我们可能会找到更短的路线.所以现在我们从伯明翰扩展.从那里我们可以去牛津(50),曼彻斯特(80),伦敦(100),纽卡斯尔(110).这首先增加了到达伯明翰的费用,这给了我们:
finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}
接下来的两个节点.牛津和伯明翰已经在完成的名单中,所以我们可以忽略它们.因此,除非从诺里奇到曼彻斯特的路线不到50英里,否则我们将在此后的迭代中到达曼彻斯特.
jet*_*hro 13
我建议你看一下具有非常实用的apporach的TopCoder教程.您需要了解STL优先级队列的工作原理,并确保negative edge weights图表中没有任何优先级队列.
可在此处找到体面的完整实施.您必须向其添加Path向量并实现RecoverPath方法,以便从源到接收器获取路径上的节点.要使用此解决方案,您还需要按以下方式转换adjacency matrix为adjacency list:
for (int i=0;i<nNodes;i++)
for (int j=0;j<nNodes;j++){
if (costMatrix[i][j] != NO_EDGE_VALUE){
G[i].pb(make_pair(j,costMatrix[i],[j]));
}
}
编辑:如果您的图表密集,我会建议您使用福特贝尔曼算法更简单,不应该慢得多.
EDIT2:要计算您应该在标题中添加的路径
int P[MAX]; /*array with links to parents*/
for(i=0; i<=nodes; i++) P[i] = -1; /*magic unset value*/
// dijkstra
while(!Q.empty()) {
....
if(!F[v] && D[u]+w < D[v]) {
D[v] = D[u] + w;
/*By setting P[v] value we will remember what is the
previous node on path from source */
P[v] = u; // <-- added line
Q.push(pii(v, D[v]));
}
...
}
然后你必须添加RecoverPath方法(仅当路径存在时才有效)
vector<int> RecoverPath(int src, int dest){
vector<int> path;
int v = dest;
while (v != src) {
path.push_back(v);
v = P[v];
}
path.push_back(src);
std::reverse(path.begin(),path.end());
return path;
}
小智 5
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <limits>
#include <set>
#include <utility>
#include <algorithm>
#include <iterator>
using namespace std;
typedef int vertex_t;
typedef double weight_t;
const weight_t max_weight = numeric_limits<double>::infinity();
struct neighbor {
vertex_t target;
weight_t weight;
neighbor(vertex_t arg_target, weight_t arg_weight)
: target(arg_target), weight(arg_weight) { }
};
typedef vector<vector<neighbor> > adjacency_list_t;
// Computing the shortest pathway
void
DijkstraComputePaths(vertex_t source,
const adjacency_list_t &adjacency_list,
vector<weight_t> &min_distance,
vector<vertex_t> &previous)
{
int n = adjacency_list.size();
min_distance.clear();
min_distance.resize(n, max_weight);
min_distance[source] = 0;
previous.clear();
previous.resize(n, -1);
set<pair<weight_t, vertex_t> > vertex_queue;
vertex_queue.insert(make_pair(min_distance[source], source));
while (!vertex_queue.empty())
{
weight_t dist = vertex_queue.begin()->first;
vertex_t u = vertex_queue.begin()->second;
vertex_queue.erase(vertex_queue.begin());
// Visit each edge exiting u
const vector<neighbor> &neighbors = adjacency_list[u];
for (vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
neighbor_iter != neighbors.end();
neighbor_iter++)
{
vertex_t v = neighbor_iter->target;
weight_t weight = neighbor_iter->weight;
weight_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v]) {
vertex_queue.erase(make_pair(min_distance[v], v));
min_distance[v] = distance_through_u;
previous[v] = u;
vertex_queue.insert(make_pair(min_distance[v], v));
}
}
} // while
}