-1
我正在研究涉及Dijkstra算法的程序。用指針向量實現Dijkstra算法
經過漫長而又漫長的搜索之後，我只找到了有關使用隊列或堆的Dijkstra算法的幫助，但是，我沒有使用這些幫助。我的任務是使用一個指向Vertex對象的指針向量（我定義的一個自定義類）。
我試圖轉換隊列僞代碼（從我的課本），以盡我最大的能力如下：
void Dijkstra(vector<Vertex*> & V, int startNum)
{
vector<Vertex*> sortedVertices = V;
sortedVertices[startNum]->setDV(0);
insertionSort(sortedVertices);
while(sortedVertices.size() != 0)
{
sortedVertices[sortedVertices.size() - 1]->setKnown(true);
sortedVertices.pop_back();
insertionSort(sortedVertices);
Vertex * v = V[1]; // Will always bring the first element off the list
v->setKnown(true);
for(int m = 0; m < sortedVertices->getAdjacentVertices().size(); m++)
{
int dist = getAdjacentVertices()[m].getWeight();
if((sortedVertices[1].getDV() + dist) < sortedVertices[m+1]->getAdjacentVertices()[m].getDV())
{
//WE WILL DECREASE THE VALUE HERE by finding the distance between two vertices
cout << "It works so far" << endl;
// BOOK has this, somehow need to change it: w.path = v
}
}
}
}
然而，當我嘗試編譯，我不斷收到以下錯誤：
Main.cpp: In function 'void Dijkstra(std::vector<Vertex*>&, int)':
Main.cpp:154:42: error: base operand of '->' has non-pointer type 'std::vector<Vertex*>'
Main.cpp:156:44: error: 'getAdjacentVertices' was not declared in this scope
Main.cpp:157:35: error: request for member 'getDV' in 'sortedVertices.std::vector<_Tp, _Alloc>::operator[]<Vertex*, std::allocator<Vertex*> >(1ul)', which is of pointer type '__gnu_cxx::__alloc_traits<std::allocator<Vertex*> >::value_type {aka Vertex*}' (maybe you meant to use '->' ?)
Main.cpp:157:99: error: '__gnu_cxx::__alloc_traits<std::allocator<Edge> >::value_type' has no member named 'getDV'
我想，以減少在這個郵編量，但如果需要可以，我的整個代碼如下：
Main.cpp的：
#include "Vertex.h"
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
void shortestPath(vector<Vertex> & v);
template <typename Comparable>
void insertionSort(vector<Comparable> & a);
template <typename Comparable>
void insertionSort(vector<Comparable> & a, int left, int right);
///overload the less than operator in order to use the stl sort for vector
///print out the path for each vertex
int main()
{
/////READ ALL THE STUFF INTO THE GRAPH////
ifstream file;
file.open("graph.txt");
cout << "Opening file..." << endl;
if(!file)
{
cout << "System failed to open file.";
}
else
{
cout << "File successfully opened" << endl;
}
int numVertices;
int numEdges;
int num;
int adjacentVertex;
int weight;
file >> numVertices;
cout << "The number of vertices that are being read into the graph from the file: " << numVertices;
cout << endl;
vector<Vertex*> vertices;
//vector<Vertex> vertices(numVertices + 1);
Vertex * newVertex;
vertices.push_back(NULL);
cout << "SIZE: " << vertices.size() << endl;
cout << "NUM VERTICES: " << numVertices << endl;
for(int i=1;i < numVertices + 1; i++)
{
file >> numEdges;
cout << "At vertex " << i << " the number of edges is " << numEdges << endl;
newVertex = new Vertex();
//Using the i counter variable in the outer for loop to identify
//the what vertex what are currently looking at in order to read in the correct adjacent vertex and weight
cout << "LENGTH OF VERTICES[i]: " << vertices.size() << endl;
newVertex->setVertexNum(i);
//newVertex.setVertexNum(i);
for(int j=1;j<=numEdges;j++)
{
file >> adjacentVertex;
cout << "The adjacent vertex is: " << adjacentVertex << endl;
file >> weight;
cout << "The weight is: " << weight << endl;
cout << endl;
newVertex->setAdjacentVertex(adjacentVertex, weight);
}
//cout << "LENGTH OF VERTICES[i]: " << vertices.size() << endl;
vertices.push_back(newVertex);
}
file.close();
vector<Vertex*> sortedVertices = vertices;
insertionSort(sortedVertices);
cout << "SIZE: " << vertices.size() << endl;
for(int i=0;i<vertices.size();i++)
{
cout << "V" << i << ": ";
cout << endl;
if(vertices[i] != NULL)
{
cout << "DV Value: " << vertices[i]->getDV();
cout << endl;
cout << "Known Value: " << vertices[i]->getKnown();
cout << endl;
}
}
cout << "Sorted: " << endl;
for(int i=0;i<sortedVertices.size();i++)
{
cout << "V" << i << ": ";
cout << endl;
if(vertices[i] != NULL)
{
cout << "DV Value: " << sortedVertices[i]->getDV();
cout << endl;
cout << "Known Value: " << sortedVertices[i]->getKnown();
cout << endl;
}
}
//CALL THE SHORTEST PATH FUNCTION ON THE GRAPH/////
}
/*
const bool myFunction(const Vertex & x, const Vertex & y)
{
return (x.getDV() >= y.getDV());
}
*/
bool operator < (const Vertex & v1, const Vertex & v2)
{
return v1.getDV() > v2.getDV();
}
void Dijkstra(vector<Vertex*> & V, int startNum)
{
vector<Vertex*> sortedVertices = V;
sortedVertices[startNum]->setDV(0);
insertionSort(sortedVertices);
while(sortedVertices.size() != 0)
{
sortedVertices[sortedVertices.size() - 1]->setKnown(true);
sortedVertices.pop_back();
insertionSort(sortedVertices);
Vertex * v = V[1]; // Will always bring the first element off the list
v->setKnown(true);
for(int m = 0; m < sortedVertices->getAdjacentVertices().size(); m++)
{
int dist = getAdjacentVertices()[m].getWeight();
if((sortedVertices[1].getDV() + dist) < sortedVertices[m+1]->getAdjacentVertices()[m].getDV())
{
//WE WILL DECREASE THE VALUE HERE by finding the distance between two vertices
cout << "It works so far" << endl;
// BOOK has this, somehow need to change it: w.path = v
}
}
}
}
////////INSERTION SORT////////////
template <typename Comparable>
void insertionSort(vector<Comparable> & a)
{
for(int p = 1; p < a.size(); ++p)
{
Comparable tmp = std::move(a[ p ]);
int j;
for(j = p; j > 0 && tmp < a[ j - 1 ]; --j)
a[ j ] = std::move(a[ j - 1 ]);
a[ j ] = std::move(tmp);
}
}
template <typename Comparable>
void insertionSort(vector<Comparable> & a, int left, int right)
{
for(int p = left + 1; p <= right; ++p)
{
Comparable tmp = std::move(a[ p ]);
int j;
for(j = p; j > left && tmp < a[ j - 1 ]; --j)
a[ j ] = std::move(a[ j - 1 ]);
a[ j ] = std::move(tmp);
}
}
Vertex.h：
#include "Edge.h"
#include <vector>
#include <climits>
#include <fstream>
using namespace std;
class Vertex
{
private:
int vertexNum; //number of the vertex for identification purposes
int degree;
bool known;
vector<Edge> adjacentVertices; //vector of vertices that are adjacent to the vertex we are currently looking at
int dv; //distance
int pv; //previous vertex
Vertex *vertex;
public:
Vertex()
{
dv = INT_MAX;
known = false;
}
void setKnown(bool Known)
{
known = Known;
}
bool getKnown()
{
return known;
}
void setVertexNum(int VertexNum)
{
vertexNum = VertexNum;
}
void setDegree(int Degree)
{
degree = Degree;
}
vector<Edge> & getAdjacentVertices()
{
return adjacentVertices;
}
int getVertexNum()
{
return vertexNum;
}
int getDegree()
{
return degree;
}
int getDV() const
{
return dv;
}
int setDV(int Dv)
{
dv = Dv;
}
void setAdjacentVertex(int AdjacentVertex, int Weight)
{
Edge newEdge;
newEdge.setWeight(Weight);
newEdge.setAdjVertex(AdjacentVertex);
adjacentVertices.push_back(newEdge);
}
friend ostream & operator <<(ostream & outstream, Vertex *vertex)
{
outstream << vertex->getVertexNum() << endl;
outstream << vertex->getDegree() << endl;
outstream << vertex->getKnown() << endl;
vector<Edge> E = vertex->getAdjacentVertices();
for(int x=0;x<E.size();x++)
{
outstream << E[x].getAdjVertex() << endl;
outstream << E[x].getWeight() << endl;
}
return outstream;
}
friend bool operator < (const Vertex & v1, const Vertex & v2);
};
Edge.h：
#include <cstdlib>
class Edge
{
private:
int adjVertex; //represents the vertex that the edge leads to
int weight;
public:
Edge()
{
adjVertex = 0;
weight = 0;
}
void setWeight(int Weight)
{
weight = Weight;
}
void setAdjVertex(int adjacent)
{
adjVertex = adjacent;
}
int getAdjVertex()
{
return adjVertex;
}
int getWeight()
{
return weight;
}
};
來吧，錯誤信息告訴你錯誤是什麼，以及它在哪裏......你還想要什麼？ –
@MarcGlisse我明白，但是當它明確指向一個向量時，爲什麼會得到非指針類型的錯誤？ – user3330599
指針向量不是指針！作爲一邊， –