var Vertex = (function(){
function Vertex(name){
this.name = name;
this.edges = [];
}

Vertex.prototype.addEdge = function(targetV,weight){
this.edges.push({target:targetV,weight:weight});
}

Vertex.prototype.getEdges = function(){
return this.edges;
}

Vertex.prototype.getName = function(){
return this.name;
}

return Vertex;
}())

var Graph = (function(){
function Graph(vertexNames,edges){
this.vertexes = this._getVertexes(vertexNames);
for(var edge of edges)
this._addEdge(...edge);
}

Graph.prototype._getVertexes = function(names){
var vertexes = {};
for(var key in names){
var name = names[key];
vertexes[name] = new Vertex(name);
}
return vertexes;
}

Graph.prototype._addEdge = function(start,end,weight){
var startVertex = this.vertexes[start];
var endVertex = this.vertexes[end];
startVertex.addEdge(endVertex, weight);
}

Graph.prototype.setTestCase = function(startVertexName,endVertexName){
this.startVertexName = startVertexName;
this.endVertexName = endVertexName;
return this;
}

Graph.prototype.execute = function(){
return this._getShortest(this.startVertexName)[this.endVertexName];
}

Graph.prototype._getShortest = function(start,isLoop = false){
isLoop || this._shortestInit(start);
var startNode = this.vertexes[start];
var table = this.table;
for(var {"target":nextNode,"weight":weight} of startNode.getEdges() ){
var thisWeight = table[nextNode.getName()]
var newWeight = table[startNode.getName()] weight
table[nextNode.getName()] = Math.min(thisWeight,newWeight);
}
this.S[start] = this.Q[start]
delete this.Q[start];

if(Object.keys(this.Q).length == 0) return table;
else {
var resultTable = this._getShortest(this._getNextVertex().getName(),true);
return resultTable;
}

}

Graph.prototype._shortestInit = function(start){
this.Q = Object.assign({},this.vertexes);
this.S = {};
this.table = this.__initTable(start);
}

Graph.prototype._getNextVertex = function(){
var minVertexName = null;
Object.keys(this.Q).forEach( QKey => {
if(!minVertexName)
minVertexName = QKey
if(this.table[minVertexName] > this.table[QKey])
minVertexName = QKey
})
return this.vertexes[minVertexName];
}

Graph.prototype.__initTable = function(start){
var rtn = {};
Object.keys(this.vertexes).forEach(v => {
rtn[v] = Infinity;
})
rtn[start] = 0;
return rtn;
}

return Graph;
}());

function init(){
var start = "A"
var end = "F"
var graph = new Graph(
["A","B","C","D","E","F"],
[
["A","B",10],
["B","E",20],
["E","F",20],
["A","C",30],
["A","D",15],
["D","C",5],
["C","F",5],
["D","F",20],
["F","D",20]
]
);
var result = graph.setTestCase(start,end).execute();
document.body.innerHTML = `점 ${start}부터 점 ${end}까지의 거리는 ${result}입니다.`;
}

init();

사랑해요 나무위키