本人实在无聊，帮你改编一下。。。
//import java.util.Random;
#include
#include
#include
using namespace std;
//c++里面没有toString()方法，下面是自己写的将int转化为string的方法
string int_to_string(int a)
{
if(a==0) return string(1,'0');
char arr[20];
int len=0;
while(a>0)
{
arr[len]=a%10+'0';
a/=10;
++len;
}
arr[len]='\0';
int harf=len/2;
--len;
char temp;
for(int i=0;i {
temp=arr[i];
arr[i]=arr[len-i];
arr[len-i]=temp;
}
return string(arr);
}
class Node{
private:
int ver;
int weight;
Node* next;
public:
Node(int x,int y,Node* next){
this->ver=x;
this->weight=y;
this->next=next;
}
int getVer() {return ver;}
void setVer(int ver) {
this->ver = ver;
}
int getWeight() {return weight;}
void setWeight(int weight) {
this->weight = weight;
}
Node* getNext() {return next;}
void setNext(Node* next) {
this->next = next;
}
};
class AgoPro2_Dijkstra_LinkedList {
public:
static void printAllPairPaths(Node** hl,int len){
for(int i=0;i dijkstraAgorithm(hl,i,len);
}
}
static void dijkstraAgorithm(Node** hl,int start,int len){
int n=len;
string* paths=new string[n];
bool* visited=new bool[n];
for(int i=0;i for(int i=0;i paths[i]=paths[i]+int_to_string(start)+"->"+int_to_string(i);
}
visited[start]=true;
for(int count=1;count<=n-1;count++){
int k=-1;
// int min=Integer.MAX_VALUE;
int min = 0x7FFFFFFF;
Node* index=hl[start];
while(index!=NULL){
if(!visited[index->getVer()]&&index->getWeight() min=index->getWeight();
k=index->getVer();
}
index=index->getNext();
}
visited[k]=true;
Node* indexK=hl[k]->getNext();
while(indexK!=NULL){
Node* indexStart=hl[start]->getNext();
while(indexStart!=NULL){
if(indexStart->getVer()==indexK->getVer()&&indexStart->getWeight()>(min+indexK->getWeight())){
indexStart->setWeight(min+indexK->getWeight());
paths[indexStart->getVer()]=paths[k]+"->"+int_to_string(indexStart->getVer());
}
indexStart=indexStart->getNext();
}
indexK=indexK->getNext();
}
}
for(int i=0;i// System.out.println("Path from "+start+" to "+i+": "+paths[i]);
cout<<"Path from "< }
}
};
class AdjListGraph{
public:
int size;
// Random rand;
Node** headList;
AdjListGraph(int size){
this->size=size;
// rand=new Random();
headList=new Node*[size];
headList=createGraph(headList,size);
}
Node** createGraph(Node** hl,int size) {
Node** tail=new Node*[size];
for(int i=0;i hl[i]=new Node(i,0,NULL);
tail[i]=hl[i];
}
for(int i=0;i for(int j=size-1;j>=i;j--){
if(i==j){
continue;
}else{
// int value=rand.nextInt(9)+1;
int value=rand()%9+1;
Node* node1=new Node(j,value,NULL);
Node* node2=new Node(i,value,NULL);
tail[i]->setNext(node1);
tail[j]->setNext(node2);
tail[i]=node1;
tail[j]=node2;
}
}
}
return hl;
}
void printGraph(){
for(int i=0;i Node* index=headList[i];
while(index!=NULL){
// System.out.print(index.getVer()+","+index.getWeight()+" ");
cout<getVer()<<','<getWeight()<<' ';
index=index->getNext();
}
// System.out.println();
cout< }
}
};
int main()
{
AdjListGraph alg(5);
alg.printGraph();
cout<<"All-pair shortest paths:"< AgoPro2_Dijkstra_LinkedList::printAllPairPaths(alg.headList,alg.size);
// system("pause");
}
主要就是几点，java里的引用转化为c++时一般用指针，对象的数组变成了指针的数组，点
（.）运算符变为->运算符（指针的调用），java有很多东西会自动初始化，比如上面的
boolean[] visited=new boolean[n];java会自动初始为false，如果c++里不显示地初始为
false就会出错了。
在c++里，数组就是一组数据，不像java那样有各种属性方法。
c++里main不在类里面
经我测试，改编的是正确的。
