// 圖的相鄰矩陣表示方法,還要用到最小值堆
#include <iostream.h>
#include <queue>
#define UNVISITED 0
#define VISITED 1
#define INFINITE 9999    //設置最大值
#define N 5 // 定義圖的頂點數

#include "Graph_matrix.h"
#include "MinHeap.h"


//[代碼7.8] Dijkstra算法
class Dist  {      //定義Dist類，下面的Dijkstra算法和Floyd算法要用到
 public:
	 int index;      //頂點的索引值，僅Dijkstra算法會用到
	 int length;     //頂點之間的距離
	 int pre;       //路徑最后經過的頂點
	 Dist() {};
	 ~Dist() {};

	 bool operator < (const Dist & arg)  {
		 return (length < arg.length);
	 }
	 bool operator == (const Dist &arg)  {
		 return (length==arg.length);
	 }
	 bool operator > (const Dist &arg)  {
		 return (length>arg.length);
	 }
	 bool operator <=(const Dist &arg)  {
		 return (length<=arg.length);
	 }
	 bool operator >= (const Dist &arg)  {
		 return (length>=arg.length);
	 }
};

//Dijkstra算法，其中參數G是圖，參數s是源頂點，D是保存最短距離及其路徑的數組
void Dijkstra(Graph& G, int s, Dist* &D)  {
	D = new Dist[G. VerticesNum()];          	// D數組
	for (int i = 0; i < G.VerticesNum(); i++) {   	// 初始化Mark數組、D數組
		G.Mark[i] = UNVISITED;
        D[i].index = i;
        D[i].length = INFINITE;
        D[i].pre = s;
    }
    D[s].length = 0; 
    MinHeap<Dist> H(G. EdgesNum());       	// 最小值堆（minheap）
    H.Insert(D[s]);
	for (i = 0; i < G.VerticesNum(); i++) {
		bool FOUND = false;
        Dist d;
        while (!H.isEmpty())  {
			d = H.RemoveMin(); 
			if(G.Mark[d.index]==UNVISITED) {                //打印出路徑信息
				cout<< "vertex index: " <<d.index<<"   ";
				cout<< "vertex pre  : " <<d.pre  <<"   ";
				cout<< "V0 --> V" << d.index <<"  length    : " <<d.length<<endl;
			}
			
			if (G.Mark[d.index] == UNVISITED) { //找到距離s最近的頂點
				FOUND = true;
				break;
			}
        }
		if (!FOUND)
            break;
        int v = d.index;
		G.Mark[v] = VISITED;           		// 把該點加入已訪問組
		// 因為v的加入，需要刷新v鄰接點的D值
		for (Edge e = G.FirstEdge(v); G.IsEdge(e);e = G.NextEdge(e))
			if (D[G.ToVertex(e)].length > (D[v].length+G.Weight(e))) {
				D[G.ToVertex(e)].length = D[v].length+G.Weight(e);
				D[G.ToVertex(e)].pre = v;
				H.Insert(D[G.ToVertex(e)]);
			}
	}
}



int A[N][N] =  {          //圖7.20  單源最短路徑的示例
//  v0  v1  v2  v3  v4  
	 0, 10,  0, 30, 100,
     0,  0, 50,  0,  0, 
     0,  0,  0,  0, 10, 
     0, 10, 20,  0, 60, 
     0,  0,  0,  0,  0, 
};

void main()
{
 Graphm aGraphm(N); // 建立圖
 aGraphm.IniGraphm(&aGraphm, A); // 初始化圖
 Dist *D;
 Dijkstra(aGraphm, 0, D);
}