Задача 13. Кратчайшие пути в графе. Алгоритм Дейкстры

По заданной матрице весов графа найти величину минимального пути и сам путь от вершины до вершины или по алгоритму Дейкстры.

№1								№2
		5	10	13						11		14	15
			8	9	13						13
				5	3	6								13
					8	10				7	11		9
						9				11	10			14

№3								№4
		5	8	7	18					6	8	11	10
			11									9	7	15
						17				8		7	14	11
		10	12		6								6	7
		7	8			11								9

№5										№6
			11	15	7							5	6	9
					14	18								3		14
		9		13	7	11	22					3		3	4	16
						11	16									4
						8	23							3		8
							19

№7								№8
		7	9		11					7	15		14
				6		13					7	16
		6		5	6							19		21
						7								17
		4		6		8				13	14	15		18

№9								№10
		10	12							7	19	20		15
			11	9		19						11	6
					10							6	9		16
			13		11	10								8	13
						6								5	15
															14

№11								№12
		7	2		13					10	11	6
					6						13	8	11	17
		2		1	3	11						5	6	15
						5							7
				3		5								9

№13								№14
		6		9	12					4	9	8
			6								2
						6								3
		4	8		6	14				2	4		6
		7	5			10				2				3

№15									№16
		5		10	8	12					6	9	13	12
			7		4	9						5	9	6
				5		6	11						6		15
							14							8	9
			6			13	21								8
				8			9

№17								№18
		8	10							11	14
			10	9	12						8	10	15
				10	12	7						11	16	20
					9	13								12
						11						11		14

№19								№20
		9	7	13							9
					15							11	5	10
		5								4		3	6	7
		6	7		8	10									5
						12						7		5	18
															4

№21								№22
		4	8							5	4		10
				3		10						8		13
		3		4	3					6		5	8
						4								8
		2		5		7						4		10

№23								№24
		12	10		11					15	10
				10	7	15							12	18
		8		7	10					10		9	12	19
						11								13
				6		12						11		14

№25
			7	12		10
					6	13
		5		4	5	6
							4
				8		5	9
							6