ekazakov/jsbin.fuyaj.coffee

## jsbin.fuyaj.coffee
console.clear()


class PQueue
  constructor: () ->
    @items = []

  add: (item) ->
    @items.push item
    @items.sort (a, b) ->
      a.compare b

  peek: ->
    if not @isEmpty() then @items[0] else null;

  poll: ->
    @items.shift()

  isEmpty: ->
    @items.length is 0

  remove: (item) ->
    index = @items.indexOf item

    if index >= 0
      @items.splice(index, 1)[0]
    else
      null;


class Vertex
  constructor: (@id, @distance = Number.POSITIVE_INFINITY, @isNotVisited = true, @edges = []) ->

  compare: (vertex) ->
    if @distance > vertex.distance
      1
    else if @distance < vertex.distance
     -1
    else
     0


class Edge
  constructor: (@target, @weight) ->


class DijkstraAlg
  constructor: (@vertexes) ->
    @queue = new PQueue
    @_initVertex vertex for vertex in @vertexes
    @queue.add vertex for vertex in @vertexes

  shortestPath: (source, target) ->
    @computePaths source
    @_traceBackPath source, target

  computePaths: (source) ->
    @_initSource source

    until @queue.isEmpty()
      vertex = @queue.poll()
      for edge in vertex.edges
        @_processEdge edge, vertex
      vertex.isNotVisited = false

  _initSource: (source) ->
    source = @queue.remove source
    source.distance = 0
    @queue.add source

  _processEdge: (edge, source) ->
    vertex = edge.target

    if vertex.isNotVisited and vertex.distance > source.distance + edge.weight
      vertex = @queue.remove vertex
      vertex.distance = source.distance + edge.weight
      vertex.previous = source
      @queue.add vertex

  _traceBackPath: (source, target) ->
    path = []
    path.unshift target

    while previous = target.previous
      path.unshift previous
      target = previous

    path

  _initVertex: (vertex) ->
    vertex.distance = Number.POSITIVE_INFINITY


###############################
# case 1
# [v0, v1, v2, v3, v4] = vertexes = [
#   new Vertex "v0"
#   new Vertex "v1"
#   new Vertex "v2"
#   new Vertex "v3"
#   new Vertex "v4"
# ]

# v0.edges = [
#   new Edge v1, 2
#   new Edge v2, 3
# #   new Edge v3, 5
# ]

# v1.edges = [ new Edge v3, 7 ]
# v2.edges = [ new Edge v4, 4 ]
# v3.edges = [ new Edge v4, 1 ]

#################################
#case 2
[v0, v1, v2, v3, v4, v5, v6, v7] = vertexes = (new Vertex "v#{i}" for i in [0..7])

v0.edges = [
  new Edge v1, 7
  new Edge v2, 4
  new Edge v3, 2
]

v1.edges = [ new Edge v4, 12 ]
v2.edges = [ new Edge v5, 9 ]
v3.edges = [
  new Edge v5, 3
  new Edge v6, 12
]
v4.edges = [
  new Edge v7, 1
  new Edge v5, 3
]
v5.edges = [
  new Edge v4, 3
  new Edge v6, 5
  new Edge v7, 2
]
v6.edges = [ new Edge v5, 5]


alg = new DijkstraAlg vertexes

console.log item.id, item.distance for item in alg.queue.items

path = alg.shortestPath v0, v4
console.log "\n===========================================\n"

console.log "path:", path.map (vertex) -> vertex.id
console.log "distance:", path[path.length - 1].distance


## jsbin.fuyaj.html
<!DOCTYPE html>
<html>
<head>
  <meta name="description" content="Dijkstra algoritm" />
  <script src="http://jashkenas.github.io/underscore/underscore-min.js"></script>
  <meta charset="utf-8">
  <title>Dijkstra algoritm</title>
</head>
<body>
</body>
</html>
	console.clear()



	class PQueue
	constructor: () ->
	@items = []

	add: (item) ->
	@items.push item
	@items.sort (a, b) ->
	a.compare b

	peek: ->
	if not @isEmpty() then @items[0] else null;

	poll: ->
	@items.shift()

	isEmpty: ->
	@items.length is 0

	remove: (item) ->
	index = @items.indexOf item

	if index >= 0
	@items.splice(index, 1)[0]
	else
	null;


	class Vertex
	constructor: (@id, @distance = Number.POSITIVE_INFINITY, @isNotVisited = true, @edges = []) ->

	compare: (vertex) ->
	if @distance > vertex.distance
	1
	else if @distance < vertex.distance
	-1
	else
	0


	class Edge
	constructor: (@target, @weight) ->


	class DijkstraAlg
	constructor: (@vertexes) ->
	@queue = new PQueue
	@_initVertex vertex for vertex in @vertexes
	@queue.add vertex for vertex in @vertexes

	shortestPath: (source, target) ->
	@computePaths source
	@_traceBackPath source, target

	computePaths: (source) ->
	@_initSource source

	until @queue.isEmpty()
	vertex = @queue.poll()
	for edge in vertex.edges
	@_processEdge edge, vertex
	vertex.isNotVisited = false

	_initSource: (source) ->
	source = @queue.remove source
	source.distance = 0
	@queue.add source

	_processEdge: (edge, source) ->
	vertex = edge.target

	if vertex.isNotVisited and vertex.distance > source.distance + edge.weight
	vertex = @queue.remove vertex
	vertex.distance = source.distance + edge.weight
	vertex.previous = source
	@queue.add vertex

	_traceBackPath: (source, target) ->
	path = []
	path.unshift target

	while previous = target.previous
	path.unshift previous
	target = previous

	path

	_initVertex: (vertex) ->
	vertex.distance = Number.POSITIVE_INFINITY


	###############################
	# case 1
	# [v0, v1, v2, v3, v4] = vertexes = [
	# new Vertex "v0"
	# new Vertex "v1"
	# new Vertex "v2"
	# new Vertex "v3"
	# new Vertex "v4"
	# ]

	# v0.edges = [
	# new Edge v1, 2
	# new Edge v2, 3
	# # new Edge v3, 5
	# ]

	# v1.edges = [ new Edge v3, 7 ]
	# v2.edges = [ new Edge v4, 4 ]
	# v3.edges = [ new Edge v4, 1 ]

	#################################
	#case 2
	[v0, v1, v2, v3, v4, v5, v6, v7] = vertexes = (new Vertex "v#{i}" for i in [0..7])

	v0.edges = [
	new Edge v1, 7
	new Edge v2, 4
	new Edge v3, 2
	]

	v1.edges = [ new Edge v4, 12 ]
	v2.edges = [ new Edge v5, 9 ]
	v3.edges = [
	new Edge v5, 3
	new Edge v6, 12
	]
	v4.edges = [
	new Edge v7, 1
	new Edge v5, 3
	]
	v5.edges = [
	new Edge v4, 3
	new Edge v6, 5
	new Edge v7, 2
	]
	v6.edges = [ new Edge v5, 5]



	alg = new DijkstraAlg vertexes

	console.log item.id, item.distance for item in alg.queue.items

	path = alg.shortestPath v0, v4
	console.log "\n===========================================\n"

	console.log "path:", path.map (vertex) -> vertex.id
	console.log "distance:", path[path.length - 1].distance
	<!DOCTYPE html>
	<html>
	<head>
	<meta name="description" content="Dijkstra algoritm" />
	<script src="http://jashkenas.github.io/underscore/underscore-min.js"></script>
	<meta charset="utf-8">
	<title>Dijkstra algoritm</title>
	</head>
	<body>
	</body>
	</html>