IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Trouver le k-ème plus court chemin


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Août 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2011
    Messages : 17
    Points : 24
    Points
    24
    Par défaut Trouver le k-ème plus court chemin
    Bonjour,

    J'ai un graphe classique avec des noeuds et des arcs. Je sais trouver facilement le chemin le plus court entre deux noeuds grâce à dijkstra. Cependant je suis amener à trouver d'autres chemins :

    -le plus court
    -le 2e plus court
    ...
    -le k-ème plus court chemin

    Un chemin est différent d'un autre si il a au moins un arc qui en diffère.

    Je n'ai pas trouver d'algorithmes efficace, malgré quelques recherches infructueuses.

    Merci pour vos futures réponses.

  2. #2
    Membre émérite
    Avatar de Franck Dernoncourt
    Homme Profil pro
    PhD student in AI @ MIT
    Inscrit en
    Avril 2010
    Messages
    894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : PhD student in AI @ MIT
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 894
    Points : 2 464
    Points
    2 464
    Par défaut
    Ce problème s'appelle le K-th Shortest Path Problem. Quelques pistes :

  3. #3
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Août 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2011
    Messages : 17
    Points : 24
    Points
    24
    Par défaut
    Salut.

    En effet, je n'avais pas pensé à chercher en anglais...

    Il y a de nombreux articles, par contre ils sont tous assez techniques (=très formels) et en anglais...
    Ca irait encore si il n'y avait pas au moins 5 versions différentes du problème sans compter le nombre d'algo pour chaque version. A un moment on me parle de "network", quelqu'un peut me dire c'est quoi le rapport entre un network (il me semble que c'est pour les flow maxi etc...) et un plus court chemin?

    Enfin bref, je vais quand même persévérer dans mes recherches. Toutefois si quelqu'un peut l'expliquer facilement ou un lien qui l'explique avec une relative simplicité, je suis preneur.

  4. #4
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    A un moment on me parle de "network", quelqu'un peut me dire c'est quoi le rapport entre un network (il me semble que c'est pour les flow maxi etc...) et un plus court chemin?
    Network c'est un réseau. Par conséquent le rapport avec des chemins n'est pas si éloigné que ça.

    Ca irait encore si il n'y avait pas au moins 5 versions différentes du problème sans compter le nombre d'algo pour chaque version.
    Bien souvent les différences sont peu nombreuses. Parfois même seule la formalisation du problème est différente. Je pense que le mieux est de te concentrer sur un algo si tu pense qu'il peut résoudre ton problème de manière pertinente. Après les p-variations entre les algos sont généralement anecdotiques.

  5. #5
    Membre émérite
    Avatar de Franck Dernoncourt
    Homme Profil pro
    PhD student in AI @ MIT
    Inscrit en
    Avril 2010
    Messages
    894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : PhD student in AI @ MIT
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 894
    Points : 2 464
    Points
    2 464
    Par défaut Code
    As-tu regardé le lien http://code.google.com/p/k-shortest-paths/ que j'avais mis dans la première réponse ? La source me semble assez bien lisible (l'algo y est notamment commenté). Tout la source en PJ de ce message. Après, comme le dit Romuald, les différences entre les variantes sont probablement anecdotiques, du moins à ton niveau (un ingénieur de Cisco, car effectivement une des applications évidentes du k-shortest-paths est le routage, ne penserait certainement pas ainsi).

    Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    ///////////////////////////////////////////////////////////////////////////////
    ///  YenTopKShortestPathsAlg.h
    ///  The implementation of Yen's algorithm to get the top k shortest paths 
    ///  connecting a pair of vertices in a graph. 
    ///
    ///  @remarks <TODO: insert remarks here>
    ///
    ///  @author Yan Qi @date 7/10/2010
    /// 
    ///  $Id: YenTopKShortestPathsAlg.h 65 2010-09-08 06:48:36Z yan.qi.asu $
    ///
    ///////////////////////////////////////////////////////////////////////////////
     
    #pragma once
     
    using namespace std;
     
    class YenTopKShortestPathsAlg
    {
    	Graph* m_pGraph;
     
    	vector<BasePath*> m_vResultList;
    	map<BasePath*, BaseVertex*> m_mpDerivationVertexIndex;
    	multiset<BasePath*, WeightLess<BasePath> > m_quPathCandidates;
     
    	BaseVertex* m_pSourceVertex;
    	BaseVertex* m_pTargetVertex;
     
    	int m_nGeneratedPathNum;
     
    private:
     
    	void _init();
     
    public:
     
    	YenTopKShortestPathsAlg(const Graph& graph)
    	{
    		YenTopKShortestPathsAlg(graph, NULL, NULL);
    	}
     
    	YenTopKShortestPathsAlg(const Graph& graph, BaseVertex* pSource, BaseVertex* pTarget)
    		:m_pSourceVertex(pSource), m_pTargetVertex(pTarget)
    	{
    		m_pGraph = new Graph(graph);
    		_init();
    	}
     
    	~YenTopKShortestPathsAlg(void){clear();}
     
    	void clear();
    	bool has_next();	
    	BasePath* next();
     
    	BasePath* get_shortest_path(BaseVertex* pSource, BaseVertex* pTarget);
    	void get_shortest_paths(BaseVertex* pSource, BaseVertex* pTarget, int top_k, 
    		vector<BasePath*>&);
    };

    Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    ///////////////////////////////////////////////////////////////////////////////
    ///  YenTopKShortestPathsAlg.cpp
    ///  The implementation of Yen's algorithm to get the top k shortest paths 
    ///  connecting a pair of vertices in a graph. 
    ///
    ///  @remarks <TODO: insert remarks here>
    ///
    ///  @author Yan Qi @date 7/10/2010
    ///
    ///  $Id: YenTopKShortestPathsAlg.cpp 65 2010-09-08 06:48:36Z yan.qi.asu $
    ///
    ///////////////////////////////////////////////////////////////////////////////
     
    #include <set>
    #include <map>
    #include <queue>
    #include <vector>
    #include "GraphElements.h"
    #include "Graph.h"
    #include "DijkstraShortestPathAlg.h"
    #include "YenTopKShortestPathsAlg.h"
     
    using namespace std;
     
    void YenTopKShortestPathsAlg::clear()
    {
    	m_nGeneratedPathNum = 0;
    	m_mpDerivationVertexIndex.clear();
    	m_vResultList.clear();
    	m_quPathCandidates.clear();
    }
     
    void YenTopKShortestPathsAlg::_init()
    {
    	clear();
    	if (m_pSourceVertex != NULL && m_pTargetVertex != NULL)
    	{
    		BasePath* pShortestPath = get_shortest_path(m_pSourceVertex, m_pTargetVertex);
    		if (pShortestPath != NULL && pShortestPath->length() > 1)
    		{
    			m_quPathCandidates.insert(pShortestPath);
    			m_mpDerivationVertexIndex[pShortestPath] = m_pSourceVertex;
    		}
    	}
    }
     
    BasePath* YenTopKShortestPathsAlg::get_shortest_path( BaseVertex* pSource, BaseVertex* pTarget )
    {
    	DijkstraShortestPathAlg dijkstra_alg(m_pGraph);
    	return dijkstra_alg.get_shortest_path(pSource, pTarget);
    }
     
    bool YenTopKShortestPathsAlg::has_next()
    {
    	return !m_quPathCandidates.empty();
    }
     
    BasePath* YenTopKShortestPathsAlg::next()
    {
    	//1. Prepare for removing vertices and arcs
    	BasePath* cur_path = *(m_quPathCandidates.begin());//m_quPathCandidates.top();
     
    	//m_quPathCandidates.pop();
    	m_quPathCandidates.erase(m_quPathCandidates.begin());
    	m_vResultList.push_back(cur_path);
     
    	int count = m_vResultList.size();
     
    	BaseVertex* cur_derivation_pt = m_mpDerivationVertexIndex.find(cur_path)->second; 
    	vector<BaseVertex*> sub_path_of_derivation_pt;
    	cur_path->SubPath(sub_path_of_derivation_pt, cur_derivation_pt);
    	int sub_path_length = sub_path_of_derivation_pt.size();
     
    	//2. Remove the vertices and arcs in the graph
    	for (int i=0; i<count-1; ++i)
    	{
    		BasePath* cur_result_path = m_vResultList.at(i);
    		vector<BaseVertex*> cur_result_sub_path_of_derivation_pt;
     
    		if (!cur_result_path->SubPath(cur_result_sub_path_of_derivation_pt, cur_derivation_pt)) continue;
     
    		if (sub_path_length != cur_result_sub_path_of_derivation_pt.size()) continue;
     
    		bool is_equal = true;
    		for (int i=0; i<sub_path_length; ++i)
    		{
    			if (sub_path_of_derivation_pt.at(i) != cur_result_sub_path_of_derivation_pt.at(i))
    			{
    				is_equal = false;
    				break;
    			}
    		}
    		if (!is_equal) continue;
     
    		//
    		BaseVertex* cur_succ_vertex = cur_result_path->GetVertex(sub_path_length+1);
    		m_pGraph->remove_edge(make_pair(cur_derivation_pt->getID(), cur_succ_vertex->getID()));
    	}
     
    	//2.1 remove vertices and edges along the current result
    	int path_length = cur_path->length();
    	for(int i=0; i<path_length-1; ++i)
    	{
    		m_pGraph->remove_vertex(cur_path->GetVertex(i)->getID());
    		m_pGraph->remove_edge(make_pair(
    			cur_path->GetVertex(i)->getID(), cur_path->GetVertex(i+1)->getID()));
    	}
     
    	//3. Calculate the shortest tree rooted at target vertex in the graph
    	DijkstraShortestPathAlg reverse_tree(m_pGraph);
    	reverse_tree.get_shortest_path_flower(m_pTargetVertex);
     
    	//4. Recover the deleted vertices and update the cost and identify the new candidates results
    	bool is_done = false;
    	for(int i=path_length-2; i>=0 && !is_done; --i)
    	{
    		//4.1 Get the vertex to be recovered
    		BaseVertex* cur_recover_vertex = cur_path->GetVertex(i);
    		m_pGraph->recover_removed_vertex(cur_recover_vertex->getID());
     
    		//4.2 Check if we should stop continuing in the next iteration
    		if (cur_recover_vertex->getID() == cur_derivation_pt->getID())
    		{
    			is_done = true;
    		}
     
    		//4.3 Calculate cost using forward star form
    		BasePath* sub_path = reverse_tree.update_cost_forward(cur_recover_vertex);
     
    		//4.4 Get one candidate result if possible
    		if (sub_path != NULL)
    		{
    			++m_nGeneratedPathNum;
     
    			//4.4.1 Get the prefix from the concerned path
    			double cost = 0;
    			reverse_tree.correct_cost_backward(cur_recover_vertex);
     
    			vector<BaseVertex*> pre_path_list;
    			for (int j=0; j<path_length; ++j)
    			{
    				BaseVertex* cur_vertex = cur_path->GetVertex(j);
    				if (cur_vertex->getID() == cur_recover_vertex->getID())
    				{
    					//j = path_length;
    					break;
    				}else
    				{
    					cost += m_pGraph->get_original_edge_weight(
    						cur_path->GetVertex(j), cur_path->GetVertex(1+j));
    					pre_path_list.push_back(cur_vertex);
    				}
    			}
    			//
    			for (int j=0; j<sub_path->length(); ++j)
    			{
    				pre_path_list.push_back(sub_path->GetVertex(j));
    			}
     
    			//4.4.2 Compose a candidate
    			sub_path = new Path(pre_path_list, cost+sub_path->Weight());
     
    			//4.4.3 Put it in the candidate pool if new
    			if (m_mpDerivationVertexIndex.find(sub_path) == m_mpDerivationVertexIndex.end())
    			{
    				m_quPathCandidates.insert(sub_path);
    				m_mpDerivationVertexIndex[sub_path] = cur_recover_vertex;
    			}
    		}
     
    		//4.5 Restore the edge
    		BaseVertex* succ_vertex = cur_path->GetVertex(i+1);
    		m_pGraph->recover_removed_edge(make_pair(cur_recover_vertex->getID(), succ_vertex->getID()));
     
    		//4.6 Update cost if necessary
    		double cost_1 = m_pGraph->get_edge_weight(cur_recover_vertex, succ_vertex)
    			+ reverse_tree.get_start_distance_at(succ_vertex);
     
    		if (reverse_tree.get_start_distance_at(cur_recover_vertex) > cost_1)
    		{
    			reverse_tree.set_start_distance_at(cur_recover_vertex, cost_1);
    			reverse_tree.set_predecessor_vertex(cur_recover_vertex, succ_vertex);
    			reverse_tree.correct_cost_backward(cur_recover_vertex);
    		}
    	}
     
    	//5. Restore everything
    	m_pGraph->recover_removed_edges();
    	m_pGraph->recover_removed_vertices();
     
    	return cur_path;
    }
     
    void YenTopKShortestPathsAlg::get_shortest_paths( BaseVertex* pSource, 
    	BaseVertex* pTarget, int top_k, vector<BasePath*>& result_list)
    {
    	m_pSourceVertex = pSource;
    	m_pTargetVertex = pTarget;
     
    	_init();
    	int count = 0; 
    	while (has_next() && count < top_k)
    	{
    		next();
    		++count;
    	}
     
    	result_list.assign(m_vResultList.begin(),m_vResultList.end());
    }

    A noter que cette implantation est apparemment critiquée sur le plan technique (mais pas algorithmique) : http://stackoverflow.com/questions/6...aths-algorithm

    Does someone know if there is any production-ready K-shortest-paths algorithm for C++?

    The only available implementation (k-shortest-paths), unfortunately, leaks memory, has counter-intuitive interfaces and another "reinvented wheel" - the Graph class.

    I'm looking for something better, probably, boost::graph-based.

    There are two possible algorithms available - simple Yen's algorithm and optimized Yen's algorithm, both would suit me.

    Thanks in advance.
    Une implémentation alternative est http://sourceforge.net/projects/ksp/files/ksp/ksp-1.0/
    Images attachées Images attachées
    Fichiers attachés Fichiers attachés

  6. #6
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Août 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2011
    Messages : 17
    Points : 24
    Points
    24
    Par défaut
    Salut,

    Franck Dernoncourt, j'ai regardé les codes que tu proposes, mais bon je suis pas trop habitué à lire des codes aussi complexes et en comprendre le principe.

    J'ai réussis néanmoins à trouver une solution pour mon problème grâce au schéma en fin de ce lien : http://malm.tuxfamily.org/doc/qr_chap3_kshortest.htm
    L'algorithme final est en fait en gros un dijkstra (en plus simple même), je ne sais pas à quel point il est performant, mais il suffit pour mon problème.

    J'essaierai d'approfondir le sujet la prochaine fois que j'en aurai besoin, merci à ceux qui ont répondu en tout cas.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Trouver l'arborescence des plus courts chemins (algorithme de Bellman-Ford)
    Par geforce dans le forum Algorithmes et structures de données
    Réponses: 12
    Dernier message: 11/03/2015, 05h39
  2. JAVA - Trouver l'arborescence des plus courts chemins
    Par geforce dans le forum Débuter avec Java
    Réponses: 4
    Dernier message: 24/02/2015, 16h11
  3. Calcul de plus court chemin dans un graphe
    Par Elmilouse dans le forum Prolog
    Réponses: 6
    Dernier message: 21/03/2010, 20h26
  4. trouver le plus court chemin dans un graphe
    Par buggen25 dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 15/08/2008, 17h34
  5. Réponses: 2
    Dernier message: 21/03/2004, 18h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo