0 Replies - 1617 Views - Last Post: 17 October 2010 - 08:54 AM

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

[LUA]Dijkstra's Algorithm

Posted 17 October 2010 - 08:54 AM

Description: simply use the NewNode,NewEdge, and SetStartNode functions to create a network of nodes then call Dijkstras to find all shortest paths to all nodes. then call GetPathTo with a mutable table and name of node you wish to find the path to and it will give you the Path in order from the start node to the requested node. finds the shortest path from a given start node to any other node int network
Nodes = {}
NodesIndex = {}
Edges = {}
SizeNodes = 0
SizeEdges = 0
StartNode = nil

local function NewNode(name)
	node = {}
	node.name = name
	node.Pre = nil
	node.Dist = -1
	node.vis = false
	Nodes[SizeNodes] = node
	NodesIndex[name] = SizeNodes
	SizeNodes = SizeNodes+1
end

local function NewEdge(Node1,Node2,EdgeVal)
	edge = {}
	edge.N1 = Node1
	edge.N2 = Node2
	edge.Dist = EdgeVal
	Edges[SizeEdges] = edge
	SizeEdges = SizeEdges+1
end

local function SetStartNode(name)
	Nodes[NodesIndex[name]].Dist = 0
	StartNode = name
end

local function EdgeConnectsNodes(E,N1,N2)
	return E.N1 == N1 and E.N2 == N2 or E.N1 == N2 and E.N2 == N1
end

local function GetDistance(N1,N2)
	for i=0,SizeEdges-1,1 do
		if EdgeConnectsNodes(Edges[i],N1,N2) then
			return Edges[i].Dist
		end
	end
	return -1
end

local function GetNumOfUnVisNodes()
	local NOUVN = 0
	for i=0,SizeNodes-1,1 do
		if not Nodes[i].vis then
			NOUVN = NOUVN + 1
		end
	end
	return NOUVN
end

local function GetAllAdjcentNodes(N,AdjNodes)
	AdjNodes.size = 0
	for i=0,SizeEdges-1,1 do
		if Edges[i].N1 == N and not Nodes[NodesIndex[Edges[i].N2]].vis then
			AdjNodes[AdjNodes.size] = Edges[i].N2
			AdjNodes.size = AdjNodes.size + 1
		elseif Edges[i].N2 == N and not Nodes[NodesIndex[Edges[i].N1]].vis then
			AdjNodes[AdjNodes.size] = Edges[i].N1
			AdjNodes.size = AdjNodes.size + 1
		end
	end
end

local function VisitClosestNode()
	local index=0
	local Dist=0
	for i=0,SizeNodes-1,1 do
		if not Nodes[i].vis and Nodes[i].Dist >= 0 then
			Dist = Nodes[i].Dist
			index=i
			break
		end
	end
	for i=0,SizeNodes-1,1 do
		if Nodes[i].Dist < Dist and not Nodes[i].vis and Nodes[i].Dist >= 0 then
			Dist = Nodes[i].Dist
			index = i
		end
	end
	Nodes[index].vis = true
	return index
end

local function Dijkstras()
	while GetNumOfUnVisNodes()>0 do
		local ClosetsNode = Nodes[VisitClosestNode()]
		local MyAdjNodes = {}
		GetAllAdjcentNodes(ClosetsNode.name,MyAdjNodes)
		local SizeAdj = MyAdjNodes.size
		for i=0,SizeAdj-1,1  do
			local Distance = ClosetsNode.Dist + GetDistance(ClosetsNode.name,MyAdjNodes[i])
			if Nodes[NodesIndex[MyAdjNodes[i]]].Dist >= 0 then
				if Distance < Nodes[NodesIndex[MyAdjNodes[i]]].Dist then
					Nodes[NodesIndex[MyAdjNodes[i]]].Dist = Distance
					Nodes[NodesIndex[MyAdjNodes[i]]].Pre = ClosetsNode.name
				end
			else
				Nodes[NodesIndex[MyAdjNodes[i]]].Dist = Distance
				Nodes[NodesIndex[MyAdjNodes[i]]].Pre = ClosetsNode.name
			end
		end
	end
end

local function GetPathTo(N,Path)
	Path.size = 0
	local CN = N
	while not (CN==StartNode) do
		local Temp = CN
		table.insert(Path,0,Temp)
		Path.size = Path.size + 1
		CN = Nodes[NodesIndex[CN]].Pre
	end
	table.insert(Path,0,StartNode)
	Path.size = Path.size + 1
end


NewNode("a")
NewNode("b")
NewNode("c")
NewNode("d")
NewNode("e")
NewNode("f")
NewNode("g")

NewEdge("a","c",10)
NewEdge("a","d",19)
NewEdge("b","c",4)
NewEdge("c","d",4)
NewEdge("b","f",41)
NewEdge("c","e",20)
NewEdge("e","f",17)
NewEdge("d","g",30)
NewEdge("g","f",4)

SetStartNode("a")

Dijkstras()

local MyPath = {}
GetPathTo("f",MyPath)

for i=0,MyPath.size-1,1 do
	print(MyPath[i])
end

os.execute("pause>nul")--this is here if you are using windows, switch to fit you needs



Is This A Good Question/Topic? 0
  • +

Replies To: [LUA]Dijkstra's Algorithm

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [LUA]Dijkstra's Algorithm

Posted 17 October 2010 - 08:54 AM

Description: simply use the NewNode,NewEdge, and SetStartNode functions to create a network of nodes then call Dijkstras to find all shortest paths to all nodes. then call GetPathTo with a mutable table and name of node you wish to find the path to and it will give you the Path in order from the start node to the requested node. finds the shortest path from a given start node to any other node int network
Nodes = {}
NodesIndex = {}
Edges = {}
StartNode = nil

push = table.insert
insert = table.insert

local function NewNode(name)
	node = {}
	node.name = name
	node.Pre = nil
	node.Dist = -1
	node.vis = false
	push(Nodes,node)
	NodesIndex[name] = #Nodes
end

local function NewEdge(Node1,Node2,EdgeVal)
	edge = {}
	edge.N1 = Node1
	edge.N2 = Node2
	edge.Dist = EdgeVal
	push(Edges,edge)
end

local function SetStartNode(name)
	Nodes[NodesIndex[name]].Dist = 0
	StartNode = name
end

local function EdgeConnectsNodes(E,N1,N2)
	return E.N1 == N1 and E.N2 == N2 or E.N1 == N2 and E.N2 == N1
end

local function GetDistance(N1,N2)
	for i=1,#Edges,1 do
		if EdgeConnectsNodes(Edges[i],N1,N2) then
			return Edges[i].Dist
		end
	end
	return -1
end

local function GetNumOfUnVisNodes()
	local NOUVN = 0
	for i=1,#Nodes,1 do
		if not Nodes[i].vis then
			NOUVN = NOUVN + 1
		end
	end
	return NOUVN
end

local function GetAllAdjcentNodes(N,AdjNodes)
	for i=1,#Edges,1 do
		if Edges[i].N1 == N and not Nodes[NodesIndex[Edges[i].N2]].vis then
			push(AdjNodes,Edges[i].N2)
		elseif Edges[i].N2 == N and not Nodes[NodesIndex[Edges[i].N1]].vis then
			push(AdjNodes,Edges[i].N1)
		end
	end
end

local function VisitClosestNode()
	local index=0
	local Dist=0
	for i=1,#Nodes,1 do
		if not Nodes[i].vis and Nodes[i].Dist >= 0 then
			Dist = Nodes[i].Dist
			index=i
			break
		end
	end
	for i=1,#Nodes,1 do
		if Nodes[i].Dist < Dist and not Nodes[i].vis and Nodes[i].Dist >= 0 then
			Dist = Nodes[i].Dist
			index = i
		end
	end
	Nodes[index].vis = true
	return index
end

local function Dijkstras()
	while GetNumOfUnVisNodes()>0 do
		local ClosetsNode = Nodes[VisitClosestNode()]
		local MyAdjNodes = {}
		GetAllAdjcentNodes(ClosetsNode.name,MyAdjNodes)
		for i=1,#MyAdjNodes,1  do
			local Distance = ClosetsNode.Dist + GetDistance(ClosetsNode.name,MyAdjNodes[i])
			local AdjNode = Nodes[NodesIndex[MyAdjNodes[i]]]
			if AdjNode.Dist >= 0 then
				if Distance < AdjNode.Dist then
					AdjNode.Dist = Distance
					AdjNode.Pre = ClosetsNode.name
				end
			else
				AdjNode.Dist = Distance
				AdjNode.Pre = ClosetsNode.name
			end
		end
	end
end

local function GetPathTo(N,Path)
	local CN = N
	while CN~=StartNode do
		local Temp = CN
		insert(Path,1,Temp)
		CN = Nodes[NodesIndex[CN]].Pre
	end
	insert(Path,1,StartNode)
end

NewNode("a")
NewNode("b")
NewNode("c")
NewNode("d")
NewNode("e")
NewNode("f")
NewNode("g")

NewEdge("a","c",10)
NewEdge("a","d",19)
NewEdge("b","c",4)
NewEdge("c","d",4)
NewEdge("b","f",41)
NewEdge("c","e",20)
NewEdge("e","f",17)
NewEdge("d","g",30)
NewEdge("g","f",4)

SetStartNode("a")

Dijkstras()

local MyPath = {}
GetPathTo("f",MyPath)
local size=#MyPath
for i=1,size,1 do
	print(MyPath[i])
end

os.execute("pause>nul")--this is here if you are using windows, switch to fit you needs


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1