191227

#include "stdafx.h"
#include <iostream>
using namespace std;
#include <iomanip>
#define size 7
#define dis 9999999
int GraphMatrix[size][size];
int distan[size];
bool visit[7] = { 0 };

void BuildMatrix(int*PathCost)
{
    int StartPoint;
    int EndPoint;
    int i, j;
    for (i = 0; i < size; i++)
    {
        for (j = 0; j < size; j++)
        {
            if (i == j)
                GraphMatrix[i][j] = 0;
            else
                GraphMatrix[i][j] = dis;
        }
    }

    i = 0;
    for (int i = 0; i < 12;i++)
    {
        StartPoint = PathCost[i * 3]-1;
        EndPoint = PathCost[i * 3 + 1]-1;
        GraphMatrix[StartPoint][EndPoint] = PathCost[i * 3 + 2];
        GraphMatrix[EndPoint][StartPoint] = PathCost[i * 3 + 2];
    }
}

void PrintGraph()
{
    int i, j;
    for (i = 0; i < size; i++)
    {
        cout << "vex" << i+1;
        for (j = 0; j < size; j++)
        {
            {
                if (GraphMatrix[i][j] == dis)
                    cout <<setw(5)<< 'x';
                else
                {
                    GraphMatrix[j][i] = GraphMatrix[i][j];
                    cout << setw(5) << GraphMatrix[i][j];
                }
            }
        }
        cout << endl;
    }
}

int find()
{
	int min = 9999999;
	for (int i = 0; i < size; i++)
	{
		if (distan[i] < min && visit[i]==0)
			min = distan[i];
	}

	return min;
}

int main(void)
{
    int PathCost[12][3] = {
        { 1, 2, 4 },
		{ 1, 3, 6 },
		{ 1, 4, 6 },
		{ 2, 3, 1 },
		{ 2, 5, 7 },
		{ 3, 4, 2 },
		{ 3, 5, 6 },
		{ 3, 6, 4 },
		{ 4, 6, 5 },
		{ 5, 6, 1 },
		{ 5, 7, 6 },
		{ 6, 7, 8 },
    };
    BuildMatrix(&PathCost[0][0]);

	for (int i = 0; i < size; i++)
		distan[i] = GraphMatrix[0][i];

	cout << "輸出distance:" << endl;
	for (int i = 0; i < size; i++)
	{
		cout << distan[i] << " ";
	}
	cout << endl;
	visit[0] = true;

	cout << "輸出[1][i]:" << endl;
	for (int i = 0; i < size; i++)
	{
		if (visit[i] == 1)
			GraphMatrix[1][i] = dis;
		cout << GraphMatrix[1][i] << " ";
	}
	cout << endl;

	cout << "找最小值" << find()<<endl;
	for (int j = 0; j < size; j++)
	{
		GraphMatrix[1][j] += find();
	}

	for (int i = 0; i < size; i++)
	{

		if (GraphMatrix[1][i] < distan[i])
			distan[i] = GraphMatrix[1][i];
	}

	for (int i = 0; i < size; i++)
		cout << distan[i] << " ";
	cout << endl;

	for (int i = 1; i < size; i++)
	{
		visit[i] = true;
		for (int j = 0; j < size; j++)
		{
			cout << "找distance最小值:" << find() << endl;
			GraphMatrix[i+1][j] += find();
			if (GraphMatrix[i + 1][j] < distan[j])
				distan[j] = GraphMatrix[i + 1][j];
		}

		cout << "輸出distance:" << endl;
		for (int i = 0; i < size; i++)
			cout << distan[i] << " ";
		cout << endl;
	}

}