خوارزمية Dijkstra - في C ++؟
https://stackoverflow.com/questions/3447566
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
خلال الأيام الأربعة الماضية ، أحاول فهم خوارزمية 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" على إجابته الممتازة
المحلول
أنصحك أن تنظر إلى TopCoder البرنامج التعليمي الذي يحتوي على Apporach براغماتية للغاية. ستحتاج إلى معرفة كيفية عمل قائمة انتظار STL الأولوية والتأكد من عدم امتلاكك negative edge weights في الرسم البياني الخاص بك.
يمكن العثور على التنفيذ الكامل لائق هنا. سيتعين عليك إضافة متجه المسار إليها وتنفيذها 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]));
}
...
}
ثم يجب عليك إضافة طريقة Recoveratph (تعمل فقط عند وجود المسار)
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;
}
نصائح أخرى
خوارزمية ديجكسترا
باللغة الإنجليزية:هذه خوارزمية للعثور على أقصر طريق من النقطة أ إلى النقطة ب.
في مصطلحات الحوسبة ، نقوم بتبسيط المسار إلى رسم بياني يتكون من العقد والأقواس. تمثل كل عقدة نقطة وسيطة بينما يقوم كل قوس بتوصيل عقدين وله وزن (غير سلبي) يمثل تكلفة اجتياز العقدتين.
لتنفيذ الخوارزمية ، تحتاج إلى قائمتين:
- الانتهاء: مجموعة من (العقدة ، التكلفة) حيث قمت بحساب الحد الأدنى للتكلفة للوصول.
- العمل: قائمة مصنفة من (العقدة ، التكلفة) التي تم فحصها.
الخوارزمية:
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) }
باستخدام مصفوفة التكاليف التالية:
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 ميلًا ، فسنصل إلى مانشستر في التكرار بعد ذلك.
#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
}
الفكرة الرئيسية لخوارزمية Dijkstra بسيطة إلى حد ما: لنفترض أن لديك مجموعة من النقاط مع أقصر مسارات معروفة إلى نقطة معينة A. ثم لنفترض أننا نريد إضافة نقطة جديدة C إلى مجموعة. دعنا نجد أي نقاط من المجموعة متصلة بنقطة نريد إضافتها. فليكن هذا النقطة ب (ط) ، لذا فإن كل نقطة ب (1) سنجد أن نجد مبلغًا من المسافة بين A إلى B (I) و B (I) و C. سيكون أصغر هذه المسافات هو الحد الأدنى بين أ و سي
التنفيذ في C ++
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000
int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;
void solve(void)
{
int i, j, k, val, x;
for(i = 2; i <= N; i++) d[i] = INF;
T.insert( mp(0, 1) );
while( T.size() > 0 )
{
val = (*T.begin()).first, x = (*T.begin()).second;
T.erase(*T.begin());
for(i = 0; i < G[x].size(); i++)
if(d[ G[x][i] ] > val + C[x][i] )
d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
}
}
int main(void)
{
freopen("dijkstra.in", "rt", stdin);
freopen("dijkstra.out", "wt", stdout);
int i, a, b, c;
scanf("%d %d\n", &N, &M);
for(i = 1; i <= M; i++)
scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);
solve();
for(i = 2; i <= N; i++)
printf("%d ", d[i] == INF ? 0 : d[i]);
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
const size_t INT_MAX = 0xFFFFFFFF; // or any other value representing infinite distance.
قم أولاً بإنشاء حافة بنية تحتوي على فهرس عقدة المصدر وفهرس عقدة الوجهة وحافة "الوزن" (الطول).
struct edge { size_t from; size_t to; size_t length; };
تحديد عقدة الفصل تحتوي على حواف للجيران المجاورة.
class Node
{
public:
void AddNeighborEdge( edge _NeighborEdge ) { m_neighborsEdges.push_back( _NeighborEdge ); }
vector<edge>::iterator FirstNeighborEdge() { return m_neighborsEdges.begin(); }
vector<edge>::iterator LastNeighborEdge() { return m_neighborsEdges.end(); }
private:
vector<edge> m_neighborsEdges;
};
سيتم استخدام NeighborSdistanceUpdator الفئة كـ "functor" بواسطة خوارزمية For_each ، للتمرير التكراري وتحديث مسافة دقيقة من العقدة الحالية في الرسم البياني إلى الجيران المجاورة.
class NeighborsDistanceUpdator
{
public:
NeighborsDistanceUpdator( vector<size_t>& _min_distance_from_source, queue< size_t >& _nodes_to_visit ) : m_min_distance_from_source( _min_distance_from_source ), m_nodes_to_visit( _nodes_to_visit )
{}
void operator()( edge& _edge )
{
size_t from = _edge.from;
size_t to = _edge.to;
if ( m_min_distance_from_source[ to ] > m_min_distance_from_source[ from ] + _edge.length )
{
m_min_distance_from_source[ to ] = m_min_distance_from_source[ from ] + _edge.length;
m_nodes_to_visit.push( to );
}
}
private:
vector<size_t>& m_min_distance_from_source;
queue< size_t >& m_nodes_to_visit;
};
أما بالنسبة لخوارزمية Dijkstra ، فما عليك سوى تشغيل جميع العقد في الرسم البياني ولكل عقدة قم بتحديث مسافة MIN من المصدر (إذا كان أقل) ، مع حفظ العقد المجاورة للزيارة.
size_t dijkstra( map< size_t, Node >& _graph, size_t _sourceIndex, size_t _targetIndex )
{
vector<size_t> min_distance_from_source( _graph.size(), INT_MAX );
min_distance_from_source[ _sourceIndex ] = 0;
queue< size_t > nodes_to_visit;
nodes_to_visit.push( _sourceIndex );
NeighborsDistanceUpdator neighborsDistanceUpdator( min_distance_from_source, nodes_to_visit );
while ( ! nodes_to_visit.empty() )
{
size_t currNodeIndex = nodes_to_visit.front();
if ( currNodeIndex == _targetIndex ) return min_distance_from_source[ currNodeIndex ];
nodes_to_visit.pop();
vector<edge>::iterator firstNeighborEdge= _graph[ currNodeIndex ].FirstNeighborEdge();
vector<edge>::iterator lastNeighborEdge= _graph[ currNodeIndex ].LastNeighborEdge();
for_each( firstNeighborEdge, lastNeighborEdge, neighborsDistanceUpdator );
}
return INT_MAX;
}
اختبار...
int main()
{
Node node1;
Node node2;
Node node3;
Node node4;
map< size_t, Node > graph;
edge ed;
ed.from = 0;
ed.to = 1;
ed.length = 1;
node1.AddNeighborEdge( ed );
cout << "node: " << 0 << " to: " << ed.to ;
cout << " lenth: " << ed.length << endl << endl;
ed.from = 0;
ed.to = 2;
ed.length = 4;
node1.AddNeighborEdge( ed );
graph.insert( make_pair( 0, node1 ) );
cout << "node: " << 0 << " to: " << ed.to ;
cout << " lenth: " << ed.length << endl << endl;
ed.from = 1;
ed.to = 2;
ed.length = 1;
node2.AddNeighborEdge( ed );
cout << "node: " << 1 << " to: " << ed.to ;
cout << " lenth: " << ed.length << endl << endl;
ed.from = 1;
ed.to = 3;
ed.length = 3;
node2.AddNeighborEdge( ed );
graph.insert( make_pair( 1, node2 ) );
cout << "node: " << 1 << " to: " << ed.to ;
cout << " lenth: " << ed.length << endl << endl;
ed.from = 2;
ed.to = 3;
ed.length = 1;
node3.AddNeighborEdge( ed );
graph.insert( make_pair( 2, node3 ) );
cout << "node: " << 2 << " to: " << ed.to ;
cout << " lenth: " << ed.length << endl << endl;
ed.from = 3;
ed.to = INT_MAX;
ed.length = INT_MAX;
node3.AddNeighborEdge( ed );
graph.insert( make_pair( 3, node4 ) );
cout << "node: " << 2 << " to: " << ed.to ;
cout << " lenth: " << ed.length << endl << endl;
cout << "min length from: 1 to 4 = " << dijkstra( graph, 0,3 ) << endl;
}
