#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

// 定義頂點(diǎn)
typedef struct EdgeNode {
	int adjvex;	// 頂點(diǎn)下標(biāo)
	struct  EdgeNode *next;	// 下一條邊的指針
	double cost;	// 當(dāng)前邊的代價(jià)

	EdgeNode();
	~EdgeNode();
} EdgeNode;


// 定義頂點(diǎn)表
typedef struct VexList
{
	string Vexs;  //用來(lái)存儲(chǔ)頂點(diǎn)信息
	EdgeNode *firstedge;  //用來(lái)存儲(chǔ)當(dāng)前頂點(diǎn)的下一個(gè)頂點(diǎn)

	VexList();
	~VexList();
} VertexList;



// 定義圖
typedef class GraphList {
public:
	GraphList();
	~GraphList();

	void PrintGraph();	// 打印圖
	void CreateGraph();	// 構(gòu)建圖

	vector<VexList> VexList;
	int Vertexs, Edges;

} GraphList;

typedef GraphList* GraphListPtr;


#endif

#include <graph.h>

EdgeNode::EdgeNode() {
	cost = 0;
	next = nullptr;
}
EdgeNode::~EdgeNode() {
	//cout << "delete Node" << endl;
}

VexList::VexList() {
	firstedge = nullptr;
}
VexList::~VexList() {
	//cout << "delete VexList" << endl;
}

GraphList::GraphList() {
	VexList.clear();
}

GraphList::~GraphList() {
	//cout << "delete GraphList" << endl;
}

void GraphList::PrintGraph() {
	cout << "所建立的地圖如以下所示：" << endl;
	for (int i = 0; i< Vertexs; i++) {
		cout << VexList[i].Vexs;             //先輸出頂點(diǎn)信息
		EdgeNode * e = VexList[i].firstedge;
		while (e) {                           //然后就開始遍歷輸出每個(gè)邊表所存儲(chǔ)的鄰接點(diǎn)的下標(biāo)
			if (e->cost == -1) {
				cout << "---->" << e->adjvex;
			}
			else {
				cout << "-- " << e->cost << " -->" << e->adjvex;
			}
			e = e->next;
		}
		cout << endl;
	}
}

void GraphList::CreateGraph() {
	EdgeNode *e = new EdgeNode();
	cout << "請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：" << endl;
	cin >> Vertexs >> Edges;
	cout << "請(qǐng)輸入頂點(diǎn)的信息：" << endl;

	for (int i = 0; i <Vertexs; ++i) {
		VertexList tmp;
		cin >> tmp.Vexs;
		tmp.firstedge = NULL;
		VexList.push_back(tmp);
	}

	for (int k = 0; k < Edges; ++k) {
		int i, j;	//(Vi，Vj)
		double cost;
		cout << "請(qǐng)輸入邊（Vi,Vj）與 cost：" << endl;
		cin >> i >> j >> cost;
		if (VexList[i].firstedge == NULL) {//當(dāng)前頂點(diǎn)i后面沒(méi)有頂點(diǎn)
			e = new EdgeNode;
			e->adjvex = j;
			e->cost = cost;
			e->next = NULL;
			VexList[i].firstedge = e;
		}
		else {  //當(dāng)前i后面有頂點(diǎn)
			EdgeNode *p = VexList[i].firstedge;
			while (p->next) {
				p = p->next;
			}
			e = new EdgeNode;
			e->adjvex = j;
			e->cost = cost;
			e->next = NULL;
			p->next = e;
		}
	}
}

#ifndef PATH_FINDER_H
#define PATH_FINDER_H

#include <iostream>
#include <graph.h>
#include <queue>

enum State{OPEN = 0, CLOSED, UNFIND};
// 定義dijkstra求解器
class DijNode {

public:
	DijNode();
	DijNode(double _val);
	~DijNode() {};
	double getCost() { return m_cost; }
	State getState() { return m_state; }
	void setCost(double _val) { m_cost = _val; }
	void setState(State _state) { m_state = _state; }
	int getIndex() { return m_index; }
	void setIndex(int _idx) { m_index = _idx; }
	void setPred(DijNode* _ptr) { preNode = _ptr; }
	DijNode* getPred() { return preNode; }

	VertexList Vertex;
private:
	int m_index;
	double m_cost;	// 起點(diǎn)到當(dāng)前點(diǎn)的代價(jià)
	State m_state;
	DijNode* preNode;	// 保存父節(jié)點(diǎn)
};

typedef DijNode* DijNodePtr;

// 構(gòu)造優(yōu)先隊(duì)列用的
struct cmp {
	bool operator() (DijNodePtr &a, DijNodePtr &b) {
		return a->getCost() > b->getCost();
	}
};

class PathFinder {
public:
	priority_queue<DijNodePtr, vector<DijNodePtr>, cmp > openList;//用優(yōu)先隊(duì)列做openList，隊(duì)首元素為最小值
	vector<DijNodePtr> m_path;	// 存放最終路徑
	PathFinder() {
		openList.empty();
		m_path.clear();
	}
	~PathFinder() {};

	void StoreGraph(GraphListPtr _graph);
	void Search(int start, int end);
	void retrievePath(DijNodePtr _ptr);

	vector<DijNodePtr> NodeList;

private:
	GraphListPtr m_graph;
	/*vector<DijNodePtr> NodeList;*/
};

typedef PathFinder* PathFinderPtr;
#endif

#include <PathFinder.h>

DijNode::DijNode() {
	m_cost = -1;	// -1表示未被探索過(guò)，距離為無(wú)窮，非負(fù)數(shù)表示已經(jīng)被探索過(guò)
	m_index = -1;
	m_state = UNFIND;	// OPEN表示openlist， CLOSED表示在closeList中，UNFIND表示未探索過(guò)
	preNode = nullptr;
}

DijNode::DijNode(double _val) {
	m_cost = _val;	// -1表示未被探索過(guò)，非負(fù)數(shù)表示已經(jīng)被探索過(guò)
	m_index = -1;
	m_state = UNFIND;	// OPEN表示openlist， CLOSED表示在closeList中，UNFIND表示未探索過(guò)
	preNode = nullptr;
}

void PathFinder::StoreGraph(GraphListPtr _graph) {
	for (int i = 0; i < _graph->VexList.size(); ++i) {
		DijNodePtr node = new DijNode();
		node->Vertex = _graph->VexList[i];
		node->setIndex(i);
		NodeList.push_back(node);
	}
}

void PathFinder::Search(int start, int end) {
	// 搜索起點(diǎn)
	DijNodePtr m_start = NodeList[start];
	m_start->setCost(0);
	m_start->setIndex(start);
	m_start->setState(OPEN);
	openList.push(m_start);

	int count = 0;
	while (!openList.empty()) {

		
		// 彈出openList中的隊(duì)首元素
		DijNodePtr cur = openList.top();
		cur->setState(CLOSED);	// 加入closelist中
		openList.pop();

		// 遍歷隊(duì)首元素所有的邊
		EdgeNode *e = cur->Vertex.firstedge;
		while (e != nullptr) {
			int _index = e->adjvex;
			double _cost = e->cost;
			
			//cout << "_cost = " << _cost << endl;
			// 如果節(jié)點(diǎn)在close list中，直接跳過(guò)
			if (NodeList[_index]->getState() == CLOSED) {
				continue;
			}

			if (NodeList[_index]->getCost() == -1) {
				NodeList[_index]->setCost(cur->getCost() + _cost);	// 更新代價(jià)
				NodeList[_index]->setPred(cur);		// 更新父節(jié)點(diǎn)
				NodeList[_index]->setState(OPEN);	// 加入open list中
				openList.push(NodeList[_index]);
			}
			else if (cur->getCost() + _cost < NodeList[_index]->getCost()) {
				// 如果從當(dāng)前節(jié)點(diǎn)到第_index個(gè)節(jié)點(diǎn)的距離更短，更新距離和父節(jié)點(diǎn)
				NodeList[_index]->setCost(cur->getCost() + _cost);	// 更新代價(jià)
				NodeList[_index]->setPred(cur);		// 更新父節(jié)點(diǎn)
				NodeList[_index]->setState(OPEN);	// 加入open list中
			}

			e = e->next;
		}
	}

	cout << "最短距離為：" << NodeList[end]->getCost() << endl;
	retrievePath(NodeList[end]);

}

void PathFinder::retrievePath(DijNodePtr ptr) {
	while (ptr != nullptr) {
		m_path.push_back(ptr);
		ptr = ptr->getPred();
	}
	reverse(m_path.begin(),m_path.end());
}

#include <graph.h>
#include <PathFinder.h>


int main() {
	cout << "構(gòu)建地圖" << endl;
	GraphListPtr graph = new GraphList();
	graph->CreateGraph();

	cout << "\n \n";
	graph->PrintGraph();

	PathFinderPtr _solver = new PathFinder();
	_solver->StoreGraph(graph);

	cout << "\n \n";

	int start, end;
	cout << "輸入起點(diǎn)" << endl;
	cin >> start;

	cout << "輸入終點(diǎn)" << endl;
	cin >> end;

	cout << "\n \n";

	_solver->Search(start, end);
	cout << "最短路徑為：";
	 
	for (int i = 0; i < _solver->m_path.size(); ++i) {
		 cout << _solver->m_path[i]->Vertex.Vexs ;
		 if (i < _solver->m_path.size() - 1)
			 cout << "-->";
	}
	cout << endl;

	system("pause");
	return 0;
}