Find shortest path in a graph
Code: "graph1_path.py". Programming language: Python
DMelt Version 1.4. Last modified: 06/13/1971. License: Pro
https://datamelt.org/code/cache/graph1_path_57.py
To run this script using the DMelt IDE,
copy the above URL link to the menu [File]→[Read script from URL] of the DMelt IDE.
# Finding a shortest distance in a graph
from jhplot import HGraph
c1 = HGraph("Canvas",600,600,1, 1)
v1="v1"
v2="v2"
v3="v3"
v4="v4"
v5="v5"
v6="v6"
v7="v7"
v8="v8"
c1.addVertex( v1 )
c1.addVertex( v2 )
c1.addVertex( v3 )
c1.addVertex( v4 )
c1.addVertex( v5 )
c1.addVertex( v6 )
c1.addVertex( v7 )
c1.addVertex( v8 )
c1.setPos( v1, 130, 40 )
c1.setPos( v2, 60, 200 )
c1.setPos( v3, 310, 330 )
c1.setPos( v4, 380, 70 )
c1.setPos( v5, 300, 150 )
c1.setPos( v6, 50, 20 )
c1.setPos( v7, 400, 380 )
c1.setPos( v8, 50, 400 )
c1.addEdge( v1, v2 )
c1.addEdge( v2, v3 )
c1.addEdge( v3, v1 )
c1.addEdge( v4, v3 )
c1.addEdge( v1, v5 )
c1.addEdge( v2, v6 )
c1.addEdge( v6, v7 )
c1.addEdge( v4, v8 )
c1.visible()
# see: http://jgrapht.org/javadoc/org/jgrapht/alg/package-summary
# http://jgrapht.org/javadoc/org/jgrapht/alg/shortestpath/package-summary
graph=c1.getListenableGraph()
print graph
from org.jgrapht import GraphTests
print "Is complete=", GraphTests.isSimple(graph)
print "Is complete=", GraphTests.isComplete(graph)
from org.jgrapht.alg.shortestpath import DijkstraShortestPath
print "Find path between ",v1, " and ", v3
d=DijkstraShortestPath(graph)
short=d.getPath(v1,v3)
# distance measured in the number of edges.
print "Shortest path=",short, " Distance=",short.getLength()
from org.jgrapht.alg.shortestpath import BidirectionalDijkstraShortestPath
print "Find bi-directional shortest path between ",v1, " and ", v3
d=BidirectionalDijkstraShortestPath(graph)
short=d.getPath(v1,v3)
print "Shortest path=",short, " Distance=",short.getLength()
You see the box below because you did not login.