Algorithme de Dijkstra avec graphe de la liste d'adjacence

Question

J'ai un graphe pondéré non orienté implémenté comme une liste d'adjacence. Il existe un hashmap avec des objets Node en tant que clés et des listes d'objets Edge en tant que valeurs. Ces objets Edge contiennent le poids du poids des arêtes entre deux nœuds. J'essaye de coder l'algorithme de plus court chemin de Dijkstra; mais je crains que ma structure graphique ne soit trop compliquée pour donner un sens à tout l'exemple/code pseudo que je peux trouver pour Dijkstra. Quelqu'un peut-il offrir de l'aide. Merci d'avance.

Answer 1

En ce qui concerne l'utilisation de Boost Graph Library, il existe également une liaison python. Je pensais Dijkstra plus court chemin est l'un de ses exemples.

Answer 2

Pour Java, plusieurs sont disponibles. JGraphT est simple et sympa. Jung, JTS etc. Si vous implémentez vous-même, alors je préfère utiliser un LinkedHashSet, ex:

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

et Vertex serait:

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

Avec être 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(); 

}