ryancarrier / dijkstra Goto Github PK

Can I access it from different goroutines almost simultaneously while the first calculation is still in progress?
My application uses this package to find a shorter path through the railroad lines and acts as a backend for a web service. If multiple requests arrive almost simultaneously, then those requests will fail.

Hi ryan:
beautiful code ! hard work ! isn't it ? if any idea about considering load balance in dijkstra algorithm? just like implemented in network router !

What if there are more than one shortest paths?
How could I get all of them?

package main

func main(){
graph:=dijkstra.NewGraph()
//Add the 3 verticies
graph.AddVertex(0)
graph.AddVertex(1)
graph.AddVertex(2)
//Add the arcs
graph.AddArc(0,1,1)
graph.AddArc(0,2,1)
graph.AddArc(1,0,1) // should be delete then print right.
graph.AddArc(1,2,2)

shortbest, err := graph.Shortest(0, 2)
if err != nil {
	log.Fatal(err)
}
fmt.Println("Shortest distance ", shortbest.Distance, " following path ", shortbest.Path)

longbest, err := graph.Longest(0, 2)
if err != nil {
	log.Fatal(err)
}
fmt.Println("Longest distance ", longbest.Distance, " following path ", longbest.Path)

}

print result:
Shortest distance 1 following path [0 2]
Longest distance 3 following path [0 1 2]

package main

import (
	"github.com/RyanCarrier/dijkstra"
	"fmt"
)

func main() {
	graph := dijkstra.NewGraph()
	graph.AddVertex(0)
	graph.AddVertex(1)
	graph.AddVertex(2)
	graph.AddVertex(3)
	graph.AddVertex(4)
	graph.AddVertex(5)
	graph.AddArc(0,1,1)
	graph.AddArc(0,3,1)
	graph.AddArc(1,2,1)
	graph.AddArc(1,4,1)
	graph.AddArc(2,5,1)
	graph.AddArc(3,4,1)
	graph.AddArc(4,2,1)
	graph.AddArc(4,5,1)
	paths, err := graph.ShortestAll(0, 5)
	if err != nil {
		panic(err)
	}
	for _, path := range paths {
		fmt.Printf("dist=%d path=%v\n", path.Distance, path.Path)
	}
}

The printed result:

dist=3 path=[0 1 4 0 3 4 5]
dist=3 path=[0 1 2 5]

So the first one is incorrect.

Would you be so kind as to include an explicit choice of OSS license for this project?

Hi buddy, i have used the project could you release the RemoveArc function in mappedGraph.go file?

How to get path through a given vertex?

How do i use the new ShortestAll function properly?

Output generated:

1
Shortest distance  1  following path  [0 2 3]

Expected output:

2
Shortest distance  1  following path  [0 1 3]
Shortest distance  1  following path  [0 2 3]

Code:

package main

import (
	"fmt"
	"github.com/RyanCarrier/dijkstra"
	"log"
)


func main() {
	graph := dijkstra.NewGraph()
	//Add the 4 verticies
	graph.AddVertex(0)

	graph.AddVertex(1)
	graph.AddVertex(2)

	graph.AddVertex(3)

	//Add the arcs
	graph.AddArc(0, 1, 1)
	graph.AddArc(0, 2, 1)

	graph.AddArc(1, 3, 0)
	graph.AddArc(2, 3, 0)

	best, err := graph.ShortestAll(0, 3)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Println(len(best))
	for _, v := range best {
		fmt.Println("Shortest distance ", v.Distance, " following path ", v.Path)

	}
}

Hello,
My programm panics (occasionally) with "invalid memory address..." when I try to call method "Shortest" for Graph struct in multiple goroutines.

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x48e1a7]

goroutine 12 [running]:
github.com/RyanCarrier/dijkstra.(*Graph).postSetupEvaluate(0xc4200ae140, 0x0, 0x2, 0xffffffffffffff01, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0)
/home/keep/work/src/github.com/RyanCarrier/dijkstra/dijkstra.go:114 +0x87
github.com/RyanCarrier/dijkstra.(*Graph).evaluate(0xc4200ae140, 0x0, 0x2, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0)
/home/keep/work/src/github.com/RyanCarrier/dijkstra/dijkstra.go:104 +0x76
github.com/RyanCarrier/dijkstra.(*Graph).Shortest(0xc4200ae140, 0x0, 0x2, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0)
/home/keep/work/src/github.com/RyanCarrier/dijkstra/dijkstra.go:7 +0x48
main.Do(0xc4200ae140)
/home/keep/main.go:34 +0x3d
created by main.main
/home/keep/main.go:29 +0x258

Is this supposed to happen? Maybe I do something wrong... If I do, what exactly?
My source code:

package main
import (
	"fmt"
	"log"

	"github.com/RyanCarrier/dijkstra"
)

func main() {
	graph := dijkstra.NewGraph()
	//Add the 3 verticies
	graph.AddVertex(0)
	graph.AddVertex(1)
	graph.AddVertex(2)
	//Add the arcs
	graph.AddArc(0, 1, 1)
	graph.AddArc(0, 2, 1)
	graph.AddArc(1, 0, 1)
	graph.AddArc(1, 2, 2)
	best, err := graph.Shortest(0, 2)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Println(best)
	for i := 0; i < 1000; i++ {
		go Do(graph)
	}
}

func Do(graph *dijkstra.Graph) {
	_, err := graph.Shortest(0, 2)
	if err != nil {
		log.Fatal(err)
	}
}

Hey, I happened to be looking at how other people implemented dijkstra's in golang. You can't use dijkstra's to solve the longest path problem. See https://en.wikipedia.org/wiki/Longest_path_problem

Hope you find this helpful!

goroutine 3403 [running]:
runtime.throw({0x8d5419?, 0x40?})
/usr/local/Cellar/go/1.19.3/libexec/src/runtime/panic.go:1047 +0x5d fp=0xc00b099568 sp=0xc00b099538 pc=0x43537d
runtime.sigpanic()
/usr/local/Cellar/go/1.19.3/libexec/src/runtime/signal_unix.go:842 +0x2c5 fp=0xc00b0995b8 sp=0xc00b099568 pc=0x44ad85
github.com/RyanCarrier/dijkstra.priorityQueueLong.Less(...)
/Users/dark/dev_lib/go/pkg/mod/github.com/!ryan!carrier/[email protected]/priority_queue.go:49
github.com/RyanCarrier/dijkstra.(*priorityQueueLong).Less(0x44c3b4?, 0x40?, 0x827d60?)
:1 +0x3f fp=0xc00b0995d8 sp=0xc00b0995b8 pc=0x7080ff
github.com/RyanCarrier/dijkstra.(*priorityQueueWrapper).down(0xc00c95aff0, 0x0, 0x9)
/Users/dark/dev_lib/go/pkg/mod/github.com/!ryan!carrier/[email protected]/priority_queue.go:128 +0x104 fp=0xc00b099620 sp=0xc00b0995d8 pc=0x707504
github.com/RyanCarrier/dijkstra.(*priorityQueueWrapper).PopOrdered(0xc00c95aff0)
/Users/dark/dev_lib/go/pkg/mod/github.com/!ryan!carrier/[email protected]/priority_queue.go:82 +0x5d fp=0xc00b099650 sp=0xc00b099620 pc=0x7072dd
github.com/RyanCarrier/dijkstra.(*Graph).postSetupEvaluate(0xc0000760a0, 0x1?, 0x326, 0x1)
/Users/dark/dev_lib/go/pkg/mod/github.com/!ryan!carrier/[email protected]/dijkstra.go:108 +0x87 fp=0xc00b0996f8 sp=0xc00b099650 pc=0x705ac7
github.com/RyanCarrier/dijkstra.(*Graph).evaluate(0x8d4972?, 0xc00c88a39c?, 0x4?, 0x1?)
/Users/dark/dev_lib/go/pkg/mod/github.com/!ryan!carrier/[email protected]/dijkstra.go:99 +0x55 fp=0xc00b099748 sp=0xc00b0996f8 pc=0x7059f5
github.com/RyanCarrier/dijkstra.(*Graph).Shortest(...)
/Users/dark/dev_lib/go/pkg/mod/github.com/!ryan!carrier/[email protected]/dijkstra.go:9
jyClient/client/resMgr.(*MapGraph).SearchPath(0xc0009c1160, 0x23b4?, 0x23bf)
/Users/dark/dev_projects/JYOline/jyClient/client/resMgr/mapGraph.go:135 +0x19f fp=0xc00b0997f0 sp=0xc00b099748 pc=0x70bcdf
jyClient/client/resMgr.(*ResMgr).GetMap2MapPath(...)
/Users/dark/dev_projects/JYOline/jyClient/client/resMgr/mapGraph.go:56
jyClient/client/resMgr.(*ResMgr).FindNearBigMap(0xc000124b40, 0x23b4, {0xca14f8?, 0x0, 0x1?})
/Users/dark/dev_projects/JYOline/jyClient/client/resMgr/resource.go:141 +0xcc fp=0xc00b099840 sp=0xc00b0997f0 pc=0x71078c
jyClient/client/scriptMgr.(*ScriptManager).cmdInternalWork(0xc009ae5020, {0xc006e39d80, 0x6}, {0x8d7342, 0x9}, {0x0, 0x0})
/Users/dark/dev_projects/JYOline/jyClient/client/scriptMgr/cmd_work.go:701 +0x1a6a fp=0xc00b0999e0 sp=0xc00b099840 pc=0x7d2b0a
jyClient/client/scriptMgr.(*ScriptManager).CMDWork(0xc009ae5020?, {0xc006e39d80?, 0xc006e39d80?}, {0x8d7342?, 0xc0000e1090?})
/Users/dark/dev_projects/JYOline/jyClient/client/scriptMgr/cmd_work.go:538 +0xd3 fp=0xc00b099a58 sp=0xc00b0999e0 pc=0x7d0f93

How can different shortest distance results exist when the same data, the same starting point and end point are calculated and tested several times

Hi,

Thanks for the amazing work regarding the Dijkstra's implementation.
I intend to use your package for a professional project. Could you tag a release in a way compatible with go mod ?

Best regards,

Alexandre