Приклади

Для одного виміру з виводом матриці суміжності:

Для 25 вимірів, 25 різних графів з 30 вершин та 100 ребер:

Таблиця часу середнього часу виконання алгоритмів пошуку для різної кількості вершин та ребер:

Кількість вершин	Кількість ребер	Час алгоритму Дейкстри, с	Час пошуку в ширину, с
10	20	0,0048	0,00352
	30	0,00336	0,00332
	40	0,00484	0,0036
30	60	0,00436	0,00428
	100	0,00524	0,00432
	200	0,00376	0,00332
	300	0,0046	0,004
100	300	0,0038	0,00356
	1000	0,0038	0,00344
	2000	0,00384	0,00324
	4000	0,00356	0,00344
500	2500	0,00508	0,0038
	5000	0,005	0,00364
	10000	0,00524	0,00352
	100000	0,00664	0,00336
1000	3000	0,01036	0,00456
	10000	0,0108	0,00412
	100000	0,01248	0,00368
	400000	0,00124	0,00328
5000	12000	0,12656	0,02148
	50000	0,13788	0,01056
	100000	0,124	0,00856
	1000000	0,152	0,00448
10000	300000	0,48348	0,06232
	500000	0,5392	0,05368
	10000000	0,5006	0,02092
	45000000	0,5038	0,0112
20000	50000	2,538	0,257
	100000	2,28	0,16032
	3000000	2,04508	0,01648
	500000000	3,23596	0,00464

Графік часу виконання алгоритмів Висновок

З графіка явно видно, що для графів з менше ніж 1000 вершин обидва алгоритми працюють однаково швидко. Проте для графів з незваженими ребрами (всі ребра довжини 1) алгоритм пошуку в ширину працює набагато швидше, ніж алгоритм Дейкстри. Проте для пошуку в графах з ребрами різної дожиниBFS не працює, а алгоритм Дейкстри розроблений саме для цього.

Використана література:

1. Роберт Седжвик: Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах

2. http://ru.wikipedia.org