Discussion :

[zamato]

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.

[Franck Dernoncourt]

Ce problème s'appelle le K-th Shortest Path Problem. Quelques pistes :

• http://stackoverflow.com/questions/6...-optimal-paths (qui pointe notamment sur http://code.google.com/p/k-shortest-paths/)
• [ame="http://www.google.fr/search?sourceid=chrome&ie=UTF-8&q=K-th+Shortest+Path+Problem"]K-th Shortest Path Problem - Recherche Google[/ame]

[zamato]

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.

[PRomu@ld]

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.

[Franck Dernoncourt]

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/

[zamato]

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.