#include?“Diagraph.h“
#include?
#include?
#include?

template?
Digraph::Digraph（?）{
???count?=0;
}

template?
int?Digraph::get_count（）{
??return?count;
}


template?
void?Digraph::readVertex（）{//讀取結點的編號極其地址
??ifstream?infile;
??infile.open（“graphVertex.txt“）;
??if（!infile）{
	??cout<<“Open?file?error!“<	??return;
??}

??int?noxy;

??infile>>no>>x>>y;
??while（infile）{
?????VertexRecord?vt（noxy）;
	?vertexList.insert（vertexList.size（）vt）;
	?infile>>no>>x>>y;
??}
}

template?
void?Digraph::read（?）
/*
Post:?A?user?specified?Digraph?has?been?read?from?the?terminal
5
0?1?3
0?2?5
1?3?5
*/
{
??ifstream?infile;
??infile.open（“graphTable.txt“）;
??if（!infile）{
	??cout<<“Open?file?error!“<	??return;
??}

??int?sdw;
??infile>>count;
??infile>>s;

??while（infile）?{
?????infile>>d>>w;
	?Vertex?v（dw）;
	?neighbors[s].insert（neighbors[s].size（）v）;?

	?infile>>s;
??}
???cout<<“okread?is?finished!“<}

template?
void?Digraph::write（?）/*
Post:?The?Digraph?has?been?printed?to?the?terminal
*/
{
	for?（int?i??=?0;?i?		int?degree?=?neighbors[i].size（）;
		cout?<		if?（degree?==?0）?
			cout?<		else?
			cout?<
		for?（int?j?=?0;?j?			Vertex?w;
			neighbors[i].retrieve（j?w）;
			cout?<			if?（j?				cout?<			else?
				cout?<		}
	}
}
	
//Dijkstra?shortest?path
template?
void?Digraph::set_distances（Vertex?source?int?distance[]int?preceding[]?/*記錄路徑信息*/）?const{
???
	int?ij;
	
	bool?found[graph_size];?//?Vertices?found?in?S

	
	//initialize?set?s;
	for?（?i?=?0;?i?		found[i]?=?false;
		distance[i]?=?infinity;
		preceding[i]?=?source.no;
	}

	//initialize?distance[]
	Vertex?x;
	for（i=0;?i
		neighbors[source.no].retrieve（ix）;??
		
		distance[x.no]?=?x.weight;

????????preceding[x.no]?=?source.no;
	}

	found[source.no]?=?true;?//?Initialize?with?vertex?source?alone?in?the?set?S.
	
	distance[source.no]?=?0;

	preceding[source.no]?=?source.no;
????
	for?（i?=?0;?i?		int?min?=?infinity;
		int?minPos=-1;
		for?（?j?=?0;?j?			if?（!found[j]）
				if?（distance[j]?					minPos?=?j;
					min?=?distance[j];
				}

		found[minPos]?=?true;

		Vertex?v（minPos0）;
		Vertex?w;
		//for?（i?=?0;?i?		for?（int?k?=?0;?k?			if?（!found[k]）{
				w.no?=?k;
				getAdjacency（vw）;

				if（min?+?w.weight?					distance[k]?=?min?+?w.weight;
				????preceding[k]?=?v.no;
				}
			}
	}
}

template?
void?Digraph