Dijkstra算法與鄰接列表圖

Question

我有一個無向，加權圖實現爲一個鄰接列表。有一個散列表，Node對象作爲鍵和Edge對象的列表作爲值。這些Edge對象包含兩個節點之間邊的權重。

我想編碼Dijkstra的最短路徑算法;但是我擔心我的圖結構太複雜，無法理解我能找到的所有Dijkstra的示例/僞代碼。任何人都可以提供幫助。提前致謝。

Answer 1

如何使用Boost Graph Library，還有python綁定它。我認爲Dijkstra最短路徑就是它的一個例子。

Answer 2

對於Java，有很多可用的。 JGraphT很簡單，很好。榮格，JTS如果要實現你自己，那我寧願使用LinkedHashSet，EX等 ：

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

和Vertex是：

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

隨着邊緣是：

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

}