PgRouting - Laptörténet

Mate, 2017. május 25., 14:52-n

2017-05-25T14:52:16Z

Szeligor: /* Telepítés */

2017-05-16T05:28:10Z

Telepítés

← Régebbi változat		A lap 2017. május 16., 05:28-kori változata
29. sor:		29. sor:

	Az adatbázis jelszóval védett és különböző felhasználókat is létre lehet benne hozni, majd a táblákról megmondani, kiknek van hozzá jogosultsága - tehát itt semmi meglepetés nincs.		Az adatbázis jelszóval védett és különböző felhasználókat is létre lehet benne hozni, majd a táblákról megmondani, kiknek van hozzá jogosultsága - tehát itt semmi meglepetés nincs.

			Grafikus megjelenítéshez a QGIS programcsomag megfelelő választás lehet.

	== Felépítés ==		== Felépítés ==

Szeligor: /* Külső hivatkozások */

2017-05-16T05:03:10Z

Külső hivatkozások

← Régebbi változat		A lap 2017. május 16., 05:03-kori változata
662. sor:		662. sor:
	* [http://workshop.pgrouting.org/index.html pgRouting Workshop]		* [http://workshop.pgrouting.org/index.html pgRouting Workshop]
	* [http://www.bostongis.com/PrinterFriendly.aspx?content_name=pgrouting_osm2po_1 OpenStreetMap fájl betöltése Osm2Po-val és útvonalkeresés]		* [http://www.bostongis.com/PrinterFriendly.aspx?content_name=pgrouting_osm2po_1 OpenStreetMap fájl betöltése Osm2Po-val és útvonalkeresés]
			* [http://docs.pgrouting.org/2.3/en/doc/index.html pgRouting v2.3 Manual]
			* [http://docs.pgrouting.org/2.3/en/doc/src/developer/sampledata.html Sample pgRouting data]
			* [https://anitagraser.com/2011/02/07/a-beginners-guide-to-pgrouting/ pgRouting guide]

Szeligor: /* Utazó ügynök probléma */

2017-05-15T20:44:08Z

Utazó ügynök probléma

@@ 532. sor: / 532. sor: @@
 === Utazó ügynök probléma ===
 Az [https://hu.wikipedia.org/wiki/Az_utaz%C3%B3_%C3%BCgyn%C3%B6k_probl%C3%A9m%C3%A1ja utazó ügynök probléma] a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására.
 === Legrövidebb utak kanyarodási korlátokkal ===

Szeligor: /* Legrövidebb utak kanyarodási korlátokkal */

2017-05-15T20:38:34Z

Legrövidebb utak kanyarodási korlátokkal

@@ 535. sor: / 535. sor: @@
 === Legrövidebb utak kanyarodási korlátokkal ===
 Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az <math>A^\ast</math> algoritmus.
 === Vezetési távolság ===

Szeligor: /* Vezetési távolság */

2017-05-15T20:32:35Z

Vezetési távolság

@@ 538. sor: / 538. sor: @@
 === Vezetési távolság ===
 Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni.
 == Kapcsolódó alkalmazások ==

Szeligor: /* Floyd-Warshall algoritmus */

2017-05-15T20:27:30Z

Floyd-Warshall algoritmus

← Régebbi változat		A lap 2017. május 15., 20:27-kori változata
462. sor:		462. sor:

	Az algoritmus költsége <math>O(\|V\|^3)</math>.		Az algoritmus költsége <math>O(\|V\|^3)</math>.

			A Floyd-Warshall algoritmus pgRouting lekérdezéseket használva:
			Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a súlyozott gráfban, mindegyiknél kiszámolva a legrövidebb utat:

			<syntaxhighlight lang="sql">
			pgr_costResult[] pgr_aspsWarshall(sql text, directed boolean, reverse_cost boolean); -- magyarul minden egyes csúcspárra kiszámolja az összes költséget.
			/*Ebben a seq a sorok szekvenciája,
			az id1 a startcsúcs azonosítója,
			az id2 a célcsúcs azonosítója,
			a cost az id1-től id2-ig jutás költsége.*/
			</syntaxhighlight>

			Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:

			<syntaxhighlight lang="sql">
			SELECT source, target, cost FROM edge_table;
			/* Ebben a source: az él startcsúcsának azonosítója,
			a target az él célcsúcsának azonosítója,
			a cost egy pozitív szám, az élen való áthaladásnak a költsége,
			a reverse_cost ha igaz, akkor a cost értékét az ellentétes irányból vesszük.*/
			</syntaxhighlight>

			Floyd-Warshall algoritmussal kiegészítve az előző lekérdezés:
			<syntaxhighlight lang="sql">
			SELECT seq, id1 AS from, id2 AS to, cost
			FROM pgr_apspWarshall(
			'SELECT id, source, target, cost FROM edge_table',
			false, false
			);
			</syntaxhighlight>

	=== Johnson algoritmus ===		=== Johnson algoritmus ===

Szeligor: /* Kétirányú A^\ast algoritmus */

2017-05-15T20:19:45Z

Kétirányú A^\ast algoritmus

← Régebbi változat		A lap 2017. május 15., 20:19-kori változata
363. sor:		363. sor:
	</syntaxhighlight>		</syntaxhighlight>

	=== Kétirányú ~~<math>~~A~~^\ast</math>~~ algoritmus ===		=== Kétirányú A* algoritmus ===
	A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.		A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.

Szeligor: /* Kétirányú A^\ast algoritmus */

2017-05-15T20:19:12Z

Kétirányú A^\ast algoritmus

← Régebbi változat		A lap 2017. május 15., 20:19-kori változata
406. sor:		406. sor:

	Reverse_cost-tal:		Reverse_cost-tal:
			<syntaxhighlight lang="sql">
	SELECT * FROM pgr_bdAStar(		SELECT * FROM pgr_bdAStar(
	'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost		'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost

Szeligor, 2017. május 15., 20:16-n

2017-05-15T20:16:17Z

← Régebbi változat		A lap 2017. május 15., 20:16-kori változata
341. sor:		341. sor:
	a source: az él startcsúcsának azonosítója,		a source: az él startcsúcsának azonosítója,
	a target az él célcsúcsának azonosítója,		a target az él célcsúcsának azonosítója,
	x1 az él start pontjának x ~~koordintátája~~,		x1 az él start pontjának x koordinátája,
	y1 az él start pontjának y koordinátája,		y1 az él start pontjának y koordinátája,
	x2 az él end pontjának x ~~koordintátája~~,		x2 az él end pontjának x koordinátája,
	y2 az él end pontjának y koordinátája,		y2 az él end pontjának y koordinátája,
	a cost egy pozitív szám, az élen való áthaladásnak a költsége,		a cost egy pozitív szám, az élen való áthaladásnak a költsége,
349. sor:		349. sor:
	</syntaxhighlight>		</syntaxhighlight>

	A*algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:		A* algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
	<syntaxhighlight lang="sql">		<syntaxhighlight lang="sql">
	SELECT * FROM pgr_AStar(		SELECT * FROM pgr_AStar(
366. sor:		366. sor:
	A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.		A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.

	~~!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!~~A Kétirányú A* algoritmus pgRouting lekérdezéseket használva:		A Kétirányú A* algoritmus pgRouting lekérdezéseket használva:
	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér.		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
374. sor:		374. sor:

	<syntaxhighlight lang="sql">		<syntaxhighlight lang="sql">
	pgr_costResult[] ~~pgr_bdDijkstra~~(sql text, source integer, target integer,		pgr_costResult[] pgr_bdAstar(sql text, source integer, target integer,
	directed boolean, has_rcost boolean);		directed boolean, has_rcost boolean);
	/*Ebben a source a startcsúcs azonosítója,		/*Ebben a source a startcsúcs azonosítója,
385. sor:		385. sor:

	<syntaxhighlight lang="sql">		<syntaxhighlight lang="sql">
	SELECT id, source, target, cost [,reverse_cost] FROM edge_table		SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table
	/* Ebben az id az él azonosítója,		/* Ebben az id az él azonosítója,
	a source: az él startcsúcsának azonosítója,		a source: az él startcsúcsának azonosítója,
	a target az él célcsúcsának azonosítója,		a target az él célcsúcsának azonosítója,
	a cost egy pozitív szám, az élen való áthaladásnak a költsége,		a cost egy pozitív szám, az élen való áthaladásnak a költsége,
			x1 az él start pontjának x koordinátája,
			y1 az él start pontjának y koordinátája,
			x2 az él end pontjának x koordinátája,
			y2 az él end pontjának y koordinátája,
	a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/		a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
	</syntaxhighlight>		</syntaxhighlight>

	~~Dijkstra~~ algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:		Kétirányú A* algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
	<syntaxhighlight lang="sql">		<syntaxhighlight lang="sql">
	SELECT ~~seq, id1 AS node, id2 AS edge, cost~~		SELECT * FROM pgr_bdAStar(
	FROM ~~pgr_bdDijkstra~~(		'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2
	'SELECT id, source, target, cost FROM edge_table',		FROM edge_table',
	7, 12, false, false		4, 10, false, false);
	);
	</syntaxhighlight>		</syntaxhighlight>

	Reverse_cost-tal:		Reverse_cost-tal:
	~~<syntaxhighlight lang="sql">~~		SELECT * FROM pgr_bdAStar(
	SELECT ~~seq, id1 AS node, id2 AS edge, cost~~		'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost
	FROM ~~pgr_bdDijkstra~~(		FROM edge_table ',
	'SELECT id, source, target, cost, reverse_cost FROM edge_table',		4, 10, true, true);
	7, 12, true, true
	);
	</syntaxhighlight>		</syntaxhighlight>

417. sor:		418. sor:
	<math>O(k\|V\|(\|E\|+\|V\|\log \|V\|))</math>.		<math>O(k\|V\|(\|E\|+\|V\|\log \|V\|))</math>.

			A Yen algoritmus pgRouting lekérdezéseket használva:
			Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, melyek utakat hoznak létre (a legrövidebb utat a két csúcs között) összesen az első k darabot.
			Ebben a seq a sorok szekvenciája,
			az id1 az út azonosítója,
			az id2 a csúcs azonosítója,
			az id3 az él azonosítója (az utolsó sorban 0)
			a cost az áthaladás költsége id2-től id3-at használva.

			Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:

			<syntaxhighlight lang="sql">
			SELECT id, source, target, cost, [,reverse_cost] FROM edge_table
			/* Ebben az id az él azonosítója,
			a source: az él startcsúcsának azonosítója,
			a target az él célcsúcsának azonosítója,
			a cost egy pozitív szám, az élen való áthaladásnak a költsége,
			a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
			</syntaxhighlight>

			Yen algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
			<syntaxhighlight lang="sql">
			SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
			FROM pgr_ksp(
			'SELECT id, source, target, cost FROM edge_table',
			7, 12, 2, false
			);
			</syntaxhighlight>

			Reverse_cost-tal:
			<syntaxhighlight lang="sql">
			SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
			FROM pgr_ksp(
			'SELECT id, source, target, cost, reverse_cost FROM edge_table',
			7, 12, 2, true
			);
			</syntaxhighlight>

	=== Floyd-Warshall algoritmus ===		=== Floyd-Warshall algoritmus ===

← Régebbi változat		A lap 2017. május 25., 14:52-kori változata
23. sor:		23. sor:
	Nem kell más, csak egy PostgreSQL és a hozzá tartozó, megfelelő verziójú PostGIS, amelyet a kapcsolódó StackBuilder-rel automatikusan, könnyen telepíthetünk.		Nem kell más, csak egy PostgreSQL és a hozzá tartozó, megfelelő verziójú PostGIS, amelyet a kapcsolódó StackBuilder-rel automatikusan, könnyen telepíthetünk.

	Elérhetőek más ~~extension-ök~~ is, én csak a PostGIS-pgRouting kombót választottam.		Elérhetőek más kiterjesztések is, én csak a PostGIS-pgRouting kombót választottam.

	Telepítés után az úgy nevezett pgAdmin alkalmazást kell elindítani és ebben kell csatlakozni az adatbázisunkhoz.		Telepítés után az úgy nevezett pgAdmin alkalmazást kell elindítani és ebben kell csatlakozni az adatbázisunkhoz.
160. sor:		160. sor:
	<math>O(\|E\|+\|V\|\log \|V\|)</math>.		<math>O(\|E\|+\|V\|\log \|V\|)</math>.

	A Dijkstra algoritmus pgRouting lekérdezéseket használva:		'''A Dijkstra algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között).		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között).
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
210. sor:		211. sor:
	A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Egy alternatív lehetőség, hogy a <math>H_s</math> és a <math>H_t</math> halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél <math>D[x]</math> kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad <math>s</math>-ből <math>t</math>-be.		A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Egy alternatív lehetőség, hogy a <math>H_s</math> és a <math>H_t</math> halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél <math>D[x]</math> kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad <math>s</math>-ből <math>t</math>-be.

	A Kétirányú Dijkstra algoritmus pgRouting lekérdezéseket használva:		'''A Kétirányú Dijkstra algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér.		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
261. sor:		263. sor:
	<math>O(\|E\|+\|V\|\log \|V\|)</math>.		<math>O(\|E\|+\|V\|\log \|V\|)</math>.

	A k-Dijkstra algoritmus pgRouting lekérdezéseket használva:		'''A k-Dijkstra algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között), vagy összeadja a költségeket (attól függ, melyik verziót használjuk).		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között), vagy összeadja a költségeket (attól függ, melyik verziót használjuk).
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
320. sor:		323. sor:
	A tapasztalat azt mutatja, hogy az <math>A^\ast</math> algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.		A tapasztalat azt mutatja, hogy az <math>A^\ast</math> algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.

	Az A* algoritmus pgRouting lekérdezéseket használva:		'''Az A* algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között). Az algoritmus Dijkstra algoritmuson alapszik, heurisztikus kikötéssel, amely hatékonyabbá teszi.		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között). Az algoritmus Dijkstra algoritmuson alapszik, heurisztikus kikötéssel, amely hatékonyabbá teszi.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
368. sor:		372. sor:
	A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.		A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.

	A Kétirányú A* algoritmus pgRouting lekérdezéseket használva:		'''A Kétirányú A* algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér.		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
421. sor:		426. sor:
	<math>O(k\|V\|(\|E\|+\|V\|\log \|V\|))</math>.		<math>O(k\|V\|(\|E\|+\|V\|\log \|V\|))</math>.

	A Yen algoritmus pgRouting lekérdezéseket használva:		'''A Yen algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, melyek utakat hoznak létre (a legrövidebb utat a két csúcs között) összesen az első k darabot.		Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, melyek utakat hoznak létre (a legrövidebb utat a két csúcs között) összesen az első k darabot.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
465. sor:		471. sor:
	Az algoritmus költsége <math>O(\|V\|^3)</math>.		Az algoritmus költsége <math>O(\|V\|^3)</math>.

	A Floyd-Warshall algoritmus pgRouting lekérdezéseket használva:		'''A Floyd-Warshall algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a súlyozott gráfban, mindegyiknél kiszámolva a legrövidebb utat:		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a súlyozott gráfban, mindegyiknél kiszámolva a legrövidebb utat:

504. sor:		511. sor:
	<math>O(\|V\|(\|E\|+\|V\|\log \|V\|))</math>.		<math>O(\|V\|(\|E\|+\|V\|\log \|V\|))</math>.

	A Johnson algoritmus pgRouting lekérdezéseket használva:		'''A Johnson algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a gráfban:		Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a gráfban:

535. sor:		543. sor:
	Az [https://hu.wikipedia.org/wiki/Az_utaz%C3%B3_%C3%BCgyn%C3%B6k_probl%C3%A9m%C3%A1ja utazó ügynök probléma] a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására.		Az [https://hu.wikipedia.org/wiki/Az_utaz%C3%B3_%C3%BCgyn%C3%B6k_probl%C3%A9m%C3%A1ja utazó ügynök probléma] a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására.

	A vezetési távolság algoritmus pgRouting lekérdezéseket használva:		'''A vezetési távolság algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) egy seq-id párossal tér vissza, amely azt írja le, mi a legjobb haladási sorrend a mátrixban, hogy eljussunk a start csúcsból a meghatározott csúcsokig.		Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) egy seq-id párossal tér vissza, amely azt írja le, mi a legjobb haladási sorrend a mátrixban, hogy eljussunk a start csúcsból a meghatározott csúcsokig.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
560. sor:		569. sor:
	Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az <math>A^\ast</math> algoritmus.		Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az <math>A^\ast</math> algoritmus.

	A legrövidebb út kanyarodási korlátokkal algoritmus pgRouting lekérdezéseket használva:		'''A legrövidebb út kanyarodási korlátokkal algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt.		Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,
609. sor:		619. sor:
	Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni.		Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni.

	A vezetési távolság algoritmus pgRouting lekérdezéseket használva:		'''A vezetési távolság algoritmus pgRouting lekérdezéseket használva:'''

	Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt.		Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt.
	Ebben a seq a sorok szekvenciája,		Ebben a seq a sorok szekvenciája,