java - 隣接リストグラフを使用したダイクストラのアルゴリズム

Question

隣接リストとして実装された無向の加重グラフがあります。Node オブジェクトをキーとして、Edge オブジェクトのリストを値として持つハッシュマップがあります。これらの Edge オブジェクトには、2 つのノード間のエッジの重みが含まれています。

ダイクストラの最短パス アルゴリズムをコーディングしようとしています。しかし、私のグラフ構造が複雑すぎて、Dijkstra で見つけたすべての例/疑似コードを理解できないのではないかと心配しています。誰でも助けを提供できますか。前もって感謝します。

Answer 1

Java の場合、多くのものが利用可能です。JGraphT はシンプルで優れています。Jung、JTSなど。自分で実装している場合は、LinkedHashSetを使用したいと思います。例:

public abstract class Graphs<T, E> 
{
final LinkedHashSet<Vertex<? extends T>> allVertex;
 ...

頂点は次のようになります。

/**
 * E is of the type: the kind of vertex I want to make. For example String

 */
 public interface Vertice<E>
  {
  public void setAttribute(E ob);
  public E getAttribute();
  //      public Set<Edge<?>> getConnectedVertices();
  public Set<Edge<?>> getConnectedEdges();       
  public Edge<?> getPassageToVertice(Vertice<?> vertice);
  }

Edge の場合:

package Graph;

   public interface Edge<E> 
   {

/**
 * Returns the attribute Associated with the Edge
 * @return The Attribute associated with the Edge
 */
public E getAttribute();

public void setSource(Vertex<?> source);

public void setDestination(Vertex<?> dest);

/**
 * Sets the attribute of the edge
 * @param attr Sets the attribute of the Edge
 */
void setAttribute(E attr);

/**
 * Get the permission to access the destination from the source.
 * <p> For example:    
 * <li>A-------edge---------B </li>
 * here A is a vertex
 *      B is a vertex
 *      edge is the edge.
 * If the argument of the method is vertex A then it returns Vertex B, if it is
 * legal to return (for ex will return B if the edge is intended to be Undirected)
 * This method can be used to create different types of Edge's.</p>
 * <p> In case of a directed edge
 * <li>A----->----edge------>B</li>
 * on calling getPassage(B) it will return null.
 * </p>
 * @param source One end of the edge
 * @return The other end of the edge if the edge has access to. Or else return null;
 */
public Vertex<?> getPassage(Vertex<?> source);

public Vertex<?> getSource();

public Vertex<?> getDestination();

}

Answer 2

Boost Graph Libraryを使用するのはどうですか。Python バインディングもあります。Dijkstra Shortest path はその例の 1 つだと思いました。