다익스트라

#include <iostream>
#include <vector>
#include <list>


using namespace std;


struct Vertex {
	int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent; // 인접 행렬

void CreateGraph() {
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][1] = 15;
	adjacent[0][3] = 35;
	
	adjacent[1][0] = 15;
	adjacent[1][2] = 5;
	adjacent[1][3] = 10;
	
	adjacent[3][4] = 5;
	adjacent[5][4] = 5;


}

void Dijikstra(int here)
{
	struct VertexCost {
		int vertex;
		int cost;
	};
	// or pair<int,int>

	list<VertexCost> discovered; // 발견 목록
	vector<int> best(6, INT32_MAX); // 각 정점별로 지금까지 발견한 최소 거리
	vector<int> parent (6,-1);

	discovered.push_back(VertexCost{here,0});
	best[here] = 0;
	parent[here] = here;
	while (discovered.empty() == false)
	{
		// 제일 좋은 후보를 찾는다.
		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;

		for (auto it = discovered.begin(); it != discovered.end(); it++)
		{
			const int cost = it->cost;

			if (cost < bestCost )
			{
				bestCost = cost;
				bestIt = it;
			}
		}

		int cost = bestIt->cost;
		here = bestIt->vertex;
		discovered.erase(bestIt);

		// 방문? 더 짧은 경로를 뒤늦게 찾았다면 스킵
		if (best[here] < cost)
			continue;

		//방문!
		for (int there = 0; there < 6; there++)
		{
			//연결되지 않았으면 스킵 
			if (adjacent[here][there] == -1)
				continue;

			//더 좋은 경로를 과거에 찾았으면 스킵
			int nextCost = best[here] + adjacent[here][there];
			if (nextCost >= best[there])
				continue;

			//(3,35) (3,25)
			discovered.push_back(VertexCost{ there,nextCost });
			best[there] = nextCost;
			parent[there] = here;
			
			
		}

	}
	int a = 3;
	for (auto i = 0; i < parent.size(); i++)
	{
		cout << parent[i] << endl;
	}
}

int main() {
	CreateGraph();
	Dijikstra(0);
}

#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;



struct Vertex {
	Vertex(int edge, int cost) : _cost(cost), _edge(edge) {

	}
	int _edge;
	int _cost;
};

vector<vector<Vertex>> adjance;

void CreateGraph(int size)
{
	adjance = vector<vector<Vertex>>(size);
	adjance[1] = { Vertex(2,2),Vertex(4,1) };
	adjance[2] = { Vertex(4,2),Vertex(3,3) };
	adjance[3] = { Vertex(6,5) };
	adjance[4] = { Vertex(5,1) };
	adjance[5] = { Vertex(6,2) };
}

void Dijikstar(int start, int end) {

	int currentEdge = start;
	cout << currentEdge << " 진입 " << endl;
	while (currentEdge < end)
	{
		int bestCost = INT32_MAX;
		int bestEdge = 0;
		for (int i = 0; i < adjance[currentEdge].size(); i++)
		{
			if (adjance[currentEdge][i]._cost < bestCost)
			{
				bestCost = adjance[currentEdge][i]._cost;
				bestEdge = adjance[currentEdge][i]._edge;
			}
		}
		currentEdge = bestEdge;
		cout << currentEdge << " 진입 " << endl;
	}
}

int main() {
	CreateGraph(7);
	Dijikstar(1, 6);

}

#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;



struct Vertex {
	Vertex(int edge, int cost) : _cost(cost), _edge(edge) {

	}
	int _edge;
	int _cost;
};

vector<vector<Vertex>> adjance;
vector<bool> discorved;
void CreateGraph(int size)
{
	adjance = vector<vector<Vertex>>(size);
	adjance[1] = { Vertex(2,2),Vertex(4,1) };
	adjance[2] = { Vertex(4,2),Vertex(3,3) };
	adjance[3] = { Vertex(6,5) };
	adjance[4] = { Vertex(5,1) };
	adjance[5] = { Vertex(6,12), Vertex(2,1)};
}

void Dijikstar(int start, int end) {
	discorved = vector<bool>(7, false);
	int currentEdge = start;
	cout << currentEdge << " 진입 " << endl;
	while (currentEdge < end)
	{
		int bestCost = INT32_MAX;
		int bestEdge = 0;
		int idx = 0;
		for (int i = 0; i < adjance[currentEdge].size(); i++)
		{
			if (discorved[adjance[currentEdge][i]._edge] == true)
				continue;
			if (adjance[currentEdge][i]._cost < bestCost)
			{
				bestCost = adjance[currentEdge][i]._cost;
				bestEdge = adjance[currentEdge][i]._edge;
				idx = i;
			}
		}
		discorved[adjance[currentEdge][idx]._edge] = true;
		currentEdge = bestEdge;
		cout << currentEdge << " 진입 " << endl;
	}
}

int main() {
	CreateGraph(7);
	Dijikstar(1, 6);

}