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

Question

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

بعد آیا مزیتی هم نسبت به الگوریتمBellman Ford  داره ؟

Answer 1

الگوریتم 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 میزاریم .

 

 

شبه کد :

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 هم تعداد راس هاست )

Answer 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);
}