 |
Find a shortest path is a weighted graph using several methods
Source code name: "graph_weighted_shortest.py"
Programming language: Python
Topic: Data mining/Graphs
DMelt Version 1.4. Last modified: 06/13/2017. License: Pro
https://datamelt.org/code/cache/graph_weighted_shortest_4793.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.
# Find a shortest path in weighted graph
from jhplot import *
g=HGraph().buildWeightedPseudograph()
v1,v2,v3,v4,v5,v6,v7 = "v1","v2","v3","v4","v5","v6","v7"
# add vertecies
g.addVertex(v1)
g.addVertex(v2)
g.addVertex(v3)
g.addVertex(v4)
g.addVertex(v5)
g.addVertex(v6)
g.addVertex(v7)
factory = g.getEdgeFactory()
e = factory.createEdge(v1,v2)
g.setEdgeWeight(e, 5)
g.addEdge(v1, v2, e)
e = factory.createEdge(v1,v2)
g.setEdgeWeight(e, 8.8)
g.addEdge(v1, v5, e)
e = factory.createEdge(v1,v2)
g.setEdgeWeight(e, 0.1)
g.addEdge(v2, v5, e)
e = factory.createEdge(v1,v3)
g.setEdgeWeight(e, 2)
g.addEdge(v1, v3, e)
e = factory.createEdge(v3,v5)
g.setEdgeWeight(e, 10.5)
g.addEdge(v3, v5, e)
e = factory.createEdge(v1,v7)
g.setEdgeWeight(e, 3)
g.addEdge(v1, v7, e)
e = factory.createEdge(v7,v5)
g.setEdgeWeight(e, 0.1)
g.addEdge(v7, v5, e)
e = factory.createEdge(v2,v6)
g.setEdgeWeight(e, 2.1)
g.addEdge(v2, v6, e)
e = factory.createEdge(v6,v5)
g.setEdgeWeight(e, 1)
g.addEdge(v6, v5, e)
e = factory.createEdge(v3,v4)
g.setEdgeWeight(e, 1)
g.addEdge(v3, v4, e)
e = factory.createEdge(v4,v5)
g.setEdgeWeight(e, 5)
g.addEdge(v4, v5, e)
HGraph().showGraph(g) # show the graph in GUI
from org.jgrapht.alg.shortestpath import BellmanFordShortestPath
print "Find weighted path between ",v1, " and ", v5
d=BellmanFordShortestPath(g,10)
short=d.getPath(v1,v5)
# distance measured in the number of edges.
print "Shortest path=",short, " Distance=",short.getLength(), "Weight=",d.getPathWeight(v1,v5)
from org.jgrapht.alg.shortestpath import KShortestPaths
print "KShortestPaths with weights path between ",v1, " and ", v5
d=KShortestPaths(g, 10)
short=d.getPaths(v1,v5)
print "List shortest path using weights:"
for l in d.getPaths(v1,v5):
print l, "length=", l.getLength(), " weight=",l.getWeight()
You see the box below because you did not login.