55.51. КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


Алгоритмы для Кратчайшего путь

	Алгоритм Дейкстры
	Алгоритм Белмана-Форда
	Алгоритм Йена
	Алгоритм Габова
	Алгоритм Джонсона


STP (Shortest Path)

INITIALIZE-SINGLE-SOURCE(G,s)
	for для всех вершин v принадлежащих V[G]
	{
		d[v] = infinity
		p[v] = NULL
	}
	d[s] = 0;


RELAX(u,v,w)
	if d[v] > d[u] + w(u,v)
	{
		d[v] = d[u] + w(u,v)
		p[v] = u
	}



  
  Алгоритм Дийкстры 
 

  



DIJKSTRA(G,w,s)
	INITIALIZE-SINGLE-SOURCE(G,s)
	S = 0
	Q = V[G]
	while (Q != {0})
	{
		u = EXTRACT_MIN(Q)
		S = S + {u}
		for для всех вершин v принадлежащих Adj[u]
		{
			RELAX(u,v,w)
		}
	}

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  





  
  Алгоритм Беллмана-Форда 
 

BELLMAN-FORD(G,w,s)
	INITIALIZE-SINGLE-SOURCE(G,s)
	for i = 1 to |V[G]|-1 
	{
		for для каждого ребра (u,v) принадлежащего E[G]
		{
			RELAX(u,w,w)
		}
	}
	for для каждого ребра (u,v) принадлежащего E[G]
	{
		if d[v] > d[u] + w(u,w)
		{
			return	false
		}
	}
	return	true

	true - в графе нет цикла отрицательного веса.
	false -  такой цикл имеется