I want to include weights or costs of the edge on my graph using this jgrapht interface-class:
package org.jgrapht;
public interface WeightedGraph<V extends Object, E extends Object> extends Graph<V, E> {
public static final double DEFAULT_EDGE_WEIGHT = 1.0;
public void setEdgeWeight(E e, double d);
}
There are exactly M edges having weight 1 and rest all the possible edges have weight 0. The array arr [] [] gives the set of edges having weight 1. The task is to calculate the total weight of the minimum spanning tree of this graph.
The weight of a path is the sum of the weights of the edges in the path. The path is A-D-B, which has edges {A,D} and {D,B}. So the weight of the path is 3+2=5. Hope this helps! How do you weight the other edges when some edges are weighted in a graph? Why are you trying to assign weights to the other edges?
A weighted directed graph is a directed graph with the added feature of each edge having a value or a weight. This weight value allows for more complex problems to be expressed through graphs. For example, you could model traffic patterns where nodes are locations, edges and their values indicate how far two locations are from each other.
Adjacency matrix representation To store weighted graph using adjacency matrix form, we call the matrix as cost matrix. Here each cell at position M [i, j] is holding the weight from edge i to j. If the edge is not present, then it will be infinity.
Yo have described Interface WeightedGraph<V,E>
from here.
You need to use SimpleDirectedWeightedGraph
to set the weights of its edges.
Look at this example, it creates Directed Weighted Graph by using graph.addVertex()
, graph.setEdgeWeight()
methods and considers
shortest path between some edges by using Dijkstra Algorithm implemented in DijkstraShortestPath.findPathBetween()
method.
import org.jgrapht.*;
import org.jgrapht.alg.*;
import org.jgrapht.graph.*;
import java.util.List;
public class Graph {
public static void main(String args[]) {
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph =
new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>
(DefaultWeightedEdge.class);
graph.addVertex("vertex1");
graph.addVertex("vertex2");
graph.addVertex("vertex3");
graph.addVertex("vertex4");
graph.addVertex("vertex5");
DefaultWeightedEdge e1 = graph.addEdge("vertex1", "vertex2");
graph.setEdgeWeight(e1, 5);
DefaultWeightedEdge e2 = graph.addEdge("vertex2", "vertex3");
graph.setEdgeWeight(e2, 3);
DefaultWeightedEdge e3 = graph.addEdge("vertex4", "vertex5");
graph.setEdgeWeight(e3, 6);
DefaultWeightedEdge e4 = graph.addEdge("vertex2", "vertex4");
graph.setEdgeWeight(e4, 2);
DefaultWeightedEdge e5 = graph.addEdge("vertex5", "vertex4");
graph.setEdgeWeight(e5, 4);
DefaultWeightedEdge e6 = graph.addEdge("vertex2", "vertex5");
graph.setEdgeWeight(e6, 9);
DefaultWeightedEdge e7 = graph.addEdge("vertex4", "vertex1");
graph.setEdgeWeight(e7, 7);
DefaultWeightedEdge e8 = graph.addEdge("vertex3", "vertex2");
graph.setEdgeWeight(e8, 2);
DefaultWeightedEdge e9 = graph.addEdge("vertex1", "vertex3");
graph.setEdgeWeight(e9, 10);
DefaultWeightedEdge e10 = graph.addEdge("vertex3", "vertex5");
graph.setEdgeWeight(e10, 1);
System.out.println("Shortest path from vertex1 to vertex5:");
List shortest_path = DijkstraShortestPath.findPathBetween(graph, "vertex1", "vertex5");
System.out.println(shortest_path);
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With