java - 如何在图形边缘包含权重？

Question

我想使用这个 jgrapht 接口类在我的图上包含边的权重或成本：

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);
}

Answer 1

哟已经Interface WeightedGraph<V,E>从这里描述了。

您需要使用SimpleDirectedWeightedGraph它来设置其边缘的权重。看这个例子，它使用 , 方法创建有向加权图，并使用 方法中实现的Dijkstra 算法考虑一些边之间的最短路径。graph.addVertex()graph.setEdgeWeight()DijkstraShortestPath.findPathBetween()

    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);

        }
    }