// Lab 4.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
#define n 11
#define size 7
struct graph
{
	int edge[n][2] = { {1,2 },{ 1,3 },{ 1,4 },{ 2,4 },{ 3,4 },{ 3,6 },{ 3,7 },{ 4,5 },{ 4,6 },{ 5,7 },{ 6,7 } };
	int w[n] = { 5,4,6,3,3,5,9,5,4,3,6 };
	int arr[size][size];
	bool v[size];
	int d[size];//расстояние между ребрами
};
void show_matrix(graph obj);
void Dijkstra(graph &obj);
int main()
{
	graph a;
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			a.arr[i][j] = 0;
		}
	}
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			for (int k = 0; k < n; k++)
			{
				if (a.edge[k][0] == i + 1 && a.edge[k][1] == j + 1)
				{
					a.arr[i][j] = a.w[k];
					a.arr[j][i] = a.w[k];
				}
			}
		}
	}
	show_matrix(a);
	for (int i = 0; i < size; i++)
	{
		a.d[i] = 999;
		a.v[i] = true;
	}
	a.d[0] = 0;
	Dijkstra(a);
	system("pause");
    return 0;
}
void show_matrix(graph obj)
{
	cout << " ";
	for (int i = 0; i < size; i++)
		cout << " " << i + 1;
	cout << endl;
	for (int i = 0; i < size; i++)
	{
		cout << i + 1 << " ";
		for (int j = 0; j < size; j++)
		{
			cout << obj.arr[i][j] << " ";
		}
		cout << endl;
	}
}
void Dijkstra(graph &obj)
{
	int min_index, min, tmp;
	do
	{
		min_index = 999, min = 999;
		for (int i = 0; i < size; i++)
		{
			if (obj.v[i] == 1 && (obj.d[i] < min))
			{
				min = obj.d[i];
				min_index = i;
			}
		}
		if (min_index != 999)
		{
			for (int i = 0; i < size; i++)
			{
				if (obj.arr[min_index][i] > 0)
				{
					tmp = min + obj.arr[min_index][i];
					if (tmp < obj.d[i])
						obj.d[i] = tmp;
				}
			}
			obj.v[min_index] = false;
		}
	} while (min_index < 999);
	cout << "The shortest distances to the vertices:" << endl;
	for (int i = 0; i < size; i++)
		cout << obj.d[i] << "  ";
	cout << endl;
}