نجوه پیاده سازی الگوریتم Dijkstra و پیدا کردن کوتاه ترین مسیر - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

نجوه پیاده سازی الگوریتم Dijkstra و پیدا کردن کوتاه ترین مسیر

+2 امتیاز
202 بازدید
الگوریتم  Dijekstra که برای پیدا کردن shortest path  داخل یک graphهست چجوری هست و چطور پیاده سازی میشه ؟

بعد آیا مزیتی هم نسبت به الگوریتمBellman Ford  داره ؟
سوال شده مهر 20, 1393  بوسیله ی َAI (امتیاز 304)   1 3 26

2 پاسخ

+2 امتیاز
 
بهترین پاسخ

الگوریتم Dijkstra و bellman ford برای پیدا کردن single source shortest path هستند وکاری که انجام میدن اینه که یک node شروع میدیم این الگوریتم ها یک آرایه شامل  طول کوتاه ترین مسیر(d)  و یک آرایه هم شامل خود مسیر ها (P) بین اون node و بقیه node های گراف بهمون میدن .

برای پیاده سازی dijekstra  :

یک آرایه برای ذخیره سازی طول مسیر ها به اندازه تعداد node های گراف میسازیم .(در آخر این آرایه return میشه .)(مثلا آرایه d )

تمام خانه های  d رو بی نهایت میزاریم .

خانه ی s آرایه d که قرار هست dijkstra روی اون انجام بشه 0 گذاشته میشه.

یک آرایه دیگه به اندازه تعداد node های گراف برای ذخیره مسیر مسازیم

راس S  رو به صف اولویت Q  اضافه می کنیم .

تا وفتی که Q خالی نشده کویکترین عنصر داخل Q رو بر میداریم(با اسم u)

       برای تمام راس های vمتصل به u 

        اگر مسیر از u به v  کوتاه تر از مسیر فعلی  راس v بود

            مسیر  v رو با مقدار جدید جایگزین می کنیم و راس v رو به Q اضافه می کنیم.

          برای ذخیره خود مسیر هم عنصر v ام آرایه P رو u میزاریم .

 

shortest path, گراف, bellman ford, dijkstra

 

شبه کد :

Dijkstra(G,w,s)  //G:graph W:tool  masir ha   s:vertex shoroo
   Initialize(G,s)  //dakhele in tabe d tamam vertex ha ro begheir az s binahayat mizarim  va d s ro 0 mizarim
   Out=0 //ras hayee ke kootah tarin masir az s beheshoon peida shode
   Q=s  //Q  priority queue hastesh va tooye in khat ras s ro mizarim dakhelesh
   While !Q.isEmpty()
       u= Q.pick_smallest() //koochik tarin onsor dakhel Q ro bar asas tool masiresh bar midarim
       Out += u 
       for each vertex v in G.adj[u]
          if  v.d>u.d + w(u,v)
            v.d>u.d + w(u,v)
            v.prevVertex = u

 

مزیتی که الگوریتم Bellman Ford داره اینه که اون برای گراف هایی که دور با وزن منفی هم دارن کار می کنه ولی dijekstra فقط روی گراف های بدون دور منفی کار می کنه

ولی در عوض Dijkstra سریع تر هست (مرتبه زمانی Dijkstra  از O(v^2 هست در حالی که bellman ford از O(v^3 ( v هم تعداد راس هاست )

پاسخ داده شده مهر 22, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
+2 امتیاز

کد ++C 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int MAX_INT = std::numeric_limits<int>::max();
typedef int Weight;
typedef int Node;

class Graph
{
public:
	Graph(int vertexNumbers) :
		adjList(vertexNumbers)
	{}
	void addEdge(int u, int v, int weight)
	{
		adjList[u].push_back(make_pair(weight, v));
	}
	vector < pair<Weight, Node>>& operator[](const Node& u)
	{
		return  adjList[u];
	}
	vector<vector<pair<Weight, Node> > > adjList;
};

void dijkstra(Graph& g, const Node& s, vector<int>& d, vector<int>& p)
{
	const int nodeNumbers = g.adjList.size();
	d.resize(nodeNumbers);
	p.resize(nodeNumbers);
	for (int i = 0; i < nodeNumbers; i++){
		p[i] = -1;
		d[i] = MAX_INT;
	}
       d[s] = 0;

	priority_queue<pair<Weight, Node> > Q;
	Q.push(make_pair(0, s));
	while (!Q.empty())
	{
		pair<int, int> elem = Q.top();
		Node u = elem.second;
		Q.pop();
		vector<pair<Weight, Node> >& adj = g[elem.second];

		for (vector<pair<Weight, Node> >::const_iterator it = adj.begin(); it != adj.end(); ++it)
		{
			Node v = it->second;
			if (it->first + d[u] < d[v])
			{
				d[v] = it->first + d[u];
				Q.push(make_pair(d[v], v));
				p[v] = u;
			}
		}
	}
}

void print_path(const vector<Node>& p, Node s, Node e)
{
	std::cout << "Going from " << s + 1 << " To " << e + 1 << ": ";
	while (e != -1 && p[e] != s)
	{
		cout << e + 1 << " ";
		e = p[e];
	}
	if (e != -1)
		cout << e + 1;
	cout << " " << s + 1 << '\n';
}
int main()
{
	Graph g(6);//graph pasokh bala

	g.addEdge(0, 1, 7);
	g.addEdge(0, 2, 9);
	g.addEdge(0, 5, 14);

	g.addEdge(1, 2, 10);
	g.addEdge(1, 3, 15);
	g.addEdge(1, 0, 7);

	g.addEdge(2, 0, 0);
	g.addEdge(2, 1, 10);
	g.addEdge(2, 3, 11);
	g.addEdge(2, 5, 2);

	g.addEdge(3, 2, 11);
	g.addEdge(3, 1, 15);
	g.addEdge(3, 4, 6);

	g.addEdge(4, 3, 6);
	g.addEdge(4, 5, 9);


	g.addEdge(5, 1, 14);
	g.addEdge(5, 2, 2);
	g.addEdge(5, 4, 9);

	vector<int> d, p;
	dijkstra(g, 0, d, p);

	int idx = 0;
	for (auto i : d)
		std::cout << "cost of Going from " << 1 << " To " << ++idx << " is : " << i << '\n';
	for (idx = 0; idx < 6; ++idx)
		print_path(p, 0, idx);
}

 

پاسخ داده شده آبان 11, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
...