如何为每个需求选择3条最短路径（源和目的地对） [英] How to select the 3 shortest paths for each demand ( pair of source & destination)
问题描述
我在我的大学里有一个项目给定了网络拓扑和需求列表（源和目标对）以获得每个需求的所有路径然后我要选择3条最短路径。因为我第一次处理编程很难知道如何正确地进行编程。
我想要做的就是获得所有可用的路径每对源和目的地之间{int sources [k] = {1,2,4,5}; int destinations [k] = {3,4,5,1}}并根据每个路径的跳数（顶点）选择每个需求[源和目标对]的3个最短可用路径。
代码可以获得每个需求的所有路径（即，s = 1& d = 3），但我不知道如何从这些可用路径中选择第1个最短3条路径，非常感谢任何帮助。 。
我尝试了什么：
I've a project in my university given the network topology and list of demands ( pair of source and destination ) to get all the paths for each demand then I've to select the 3 shortest paths. since its my first time to deal with programming its kind of difficult to know how to do it correctly.
what i'm trying to do is to get all available paths between each pair of source and destination { int sources[k]={1,2,4,5}; int destinations[k]={3,4,5,1} } and according to number of hops ( vertices ) of each path select the 3 shortest out of available paths for each demand [ pair of source and destination ].
the code can get all paths for each demand (i.e., s=1& d=3 ) but i don't know how to select out of these available paths the 1st shortest 3 paths, Any help is very appreciated. .
What I have tried:
// C++ program to print all paths from a source to destination.
#include<iostream>
#include <list>
using namespace std;
// A directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices in graph
list<int> *adj; // Pointer to an array containing adjacency lists
// A recursive function used by printAllPaths()
void printAllPathsUtil(int , int, bool [], int [], int &);
public:
Graph(int V); // Constructor
void addEdge(int u, int v);
void printAllPaths(int s, int d);
void printShortestPaths(int s, int d);
int k;
int sources;
int destinations;
int id=0;
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v); // Add v to u’s list.
}
// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
// Create an array to store paths
int *path = new int[V];
int path_index = 0; // Initialize path[] as empty
// Initialize all vertices as not visited
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print all paths
printAllPathsUtil(s, d, visited, path, path_index);
}
// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[],
int path[], int &path_index)
{
int id_path[40][V-1]; //40 is an example as maximum number of paths
bool id_hops[40];
for (int i = 0; i< 40; i++)
for (int j = 0; j< V-1; j++)
id_path [i][j]=0;
for (int i = 0; i< 40; i++)
id_hops [i]=0;
// Mark the current node and store it in path[]
visited[u] = true;
path[path_index] = u;
path_index++;
int hops = path_index -1;
// If current vertex is same as destination, then print
// current path[]
if (u == d)
{
if(hops && path)
id++;
id_hops[id-1]= hops;
for (int i = 0; i< path_index; i++)
if (path[i]!=0)
id_path[id-1][i]=path[i];
cout << "Path_ID = " << id << " Path is : ";
for (int i = 0; i< path_index; i++)
cout << path[i] << " ";
cout << "Number of hops = " << hops << endl;
}
else // If current vertex is not destination
{
// Recur for all the vertices adjacent to current vertex
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path, path_index);
}
// Remove current vertex from path[] and mark it as unvisited
path_index--;
visited[u] = false;
int id_Sorted[3]; //id_Sorted contains the 3 ids of the shortest paths
for (int j=0; j<3; j++)
id_Sorted[j]=0;
//we select these 3 ids
int min=0; //the shortest
for (int j=0; j<2; j++)
{
for (int i=1; i<40; i++)
if ((i!= id_Sorted[0])&& (i!= id_Sorted[1]))
{
if (id_hops[i]< id_hops[min])
min=i;
}
id_Sorted[j]=min;
}
//creation of id_pathShort
int id_pathShort[3][V-1];
for (int j=0; j <= 2; j++)
{
cout << "Path_ID_Short = " << j << " Path_short is : ";
for (int i=0; i<V-1; i++)
{
id_pathShort[j][i]=id_path[id_Sorted[j]][i];
if (id_pathShort[j][i])
cout << id_pathShort[j][i] << " ";
}
cout << "Number of hops_short = " << id_hops[id_Sorted[j]] << endl;
}
}
// Driver program
int main()
{
// Create a graph given in the above diagram
Graph g(7);
g.addEdge(1, 2);
g.addEdge(2, 1);
g.addEdge(1, 6);
g.addEdge(6, 1);
g.addEdge(2, 6);
g.addEdge(6, 2);
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(3, 5);
g.addEdge(5, 3);
g.addEdge(4, 5);
g.addEdge(5, 4);
g.addEdge(5, 6);
g.addEdge(6, 5);
for (int k=0;k<=2; k++)
{ int sources[k]={1,2,4,5};
int destinations[k]={3,4,5,1};
int s= sources[k];
int d= destinations[k];
if( true){
cout << "Following are all different paths from " << s
<< " to " << d << endl;
g.printAllPaths(s, d);
}
};
return 0;
}
推荐答案
当你有了pathes时，你必须实现一些计算长度的代码。比较。听起来很简单...
开头：节点与节点之间的边长是多少。
When you have the pathes you must implement some code which calculates the length. Than compare. Sounds so easy...
Start with: what length has an edge between to nodes than sum up.
这篇关于如何为每个需求选择3条最短路径（源和目的地对）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
