Question

用C++创建一个图，并寻找最短路径

题目要求：
1、用C++创建一个图，由于我现在只有1级，所以不能上传图片，麻烦大家给我一段创建图的代码，或者给我连接也行。
2、找出各条路径的最佳路径（最短路径），运行程序的时候，输入起点和终点要能直接显示出这条最短路径。
补充下：老师给我们的要求是在学校选取10个点，创建一个平面图，并找出最短路径。
我们那书上讲得很少，只有一点概念，没有创建图的代码，我更不知道怎么才能找出最短路径，麻烦高手给我个思路，和一些资料。

Answer 1

下面这个是我以前做的，你可以参考一下。
用VC++建一个工程，根据你的需要，修改邻接矩阵就可以了；源代码如下：
// Stack.h: interface for the Stack class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_)
#define AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_

#include<iostream.h>

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define MaxSize 1024

template <class Type> class Stack{//堆栈类
private:
Type data[MaxSize];
int top;
public:
Stack(){ //初始化栈
top = -1;
}
virtual~Stack();
bool IsEmpty(); //判断栈为空
bool IsFull(); //判断栈为满
int GetTop(); //取top的位置
void Push(Type);//进栈
Type Pop(); //退栈
};

template <class Type> Stack<Type>::~Stack(){

}

template <class Type> bool Stack<Type>::IsEmpty(){
return(top == -1);
}

template <class Type> bool Stack<Type>::IsFull(){
return(top == MaxSize-1);
}

template <class Type> int Stack<Type>::GetTop(){
return top;
}

template <class Type> void Stack<Type>::Push(Type item){
if(IsFull())
cout<<"栈满!\n";
else{
top++;
data[top] = item;
}
}

template <class Type> Type Stack<Type>::Pop(){
if(IsEmpty()){
cout<<"栈空!\n";
return NULL;
}
else{
Type item;
item = data[top];
top--;
return item;
}
}

#endif // !defined(AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_)
// AdjMatrix.h: interface for the AdjMatrix class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_)
#define AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_

#include <iostream.h>
#include <iomanip.h>
#include "Stack.h"

#define INT_MAX 0x7FFFFFFF

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template <class Type>
void Make2DArray(Type ** & x,int rows,int cols){//创建二维数组x
x = new Type *[rows];//创建行指针
for(int i = 0;i < rows;i++)//为每一行分配空间
x[i] = new Type[cols];
}

template <class Type>
void Delete2DArray(Type ** & x,int rows){//删除二维数组x
for(int i = 0;i < rows;i++)//释放为每一行所分配的空间
delete[]x[i];
delete[]x;//删除行指针
x = NULL;
}

class AdjMatrix{//方阵类
double **a;//数据缓存区
public:
AdjMatrix(double **b = NULL,int dimention = 0){//初始化方阵
Make2DArray(a,dimention+1,dimention+1);
a[0][0] = dimention;
for(int i = 1,j = 1;i <= dimention,j <= dimention;i++,j++){
a[i][0] = 0;
a[0][j] = 0;
}
if(b)
for(int i1 = 1;i1 <= dimention;i1++)
for(int j1 = 1;j1 <= dimention;j1++)
a[i1][j1] = b[i1-1][j1-1];
}
virtual ~AdjMatrix();//析构函数
AdjMatrix & operator = (const AdjMatrix &);//重载赋值运算符=
void Trs(AdjMatrix &);//矩阵转置:B=trs(*this)
void Show();//显示结果
void ShortestPath_Floyed();//弗洛伊德算法，求每对顶点之间的最短路径
void ShortestPath_Dijkstra(int);//狄克斯特拉算法，求单源最短路径
//输入v为源点编号
};
#endif // !defined(AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_)
// AdjMatrix.cpp: implementation of the AdjMatrix class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AdjMatrix.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

AdjMatrix::~AdjMatrix(){
int Dim = (int)a[0][0]+1;
Delete2DArray(a,Dim);
}

AdjMatrix & AdjMatrix::operator = (const AdjMatrix &matrix){
int Dim1 = (int)a[0][0],Dim2 = (int)matrix.a[0][0];
Delete2DArray(a,Dim1+1);
Make2DArray(a,Dim2+1,Dim2+1);
for(int i = 0;i <= Dim2;i++)
for(int j = 0;j <= Dim2;j++)
a[i][j] = matrix.a[i][j];
return *this;
}

void AdjMatrix::Trs(AdjMatrix &B){
int Dim1 = (int)a[0][0],Dim2 = (int)B.a[0][0];
Delete2DArray(B.a,Dim2+1);
Make2DArray(B.a,Dim1+1,Dim1+1);
B.a[0][0] = Dim1;
for(int i = 1,j = 1;i <= Dim1,j <= Dim1;i++,j++){
B.a[i][0] = 0;
B.a[0][j] = 0;
}
for(int i1 = 1;i1 <= Dim1;i1++)
for(int j1 = 1;j1 <= Dim1;j1++)
B.a[i1][j1] = a[j1][i1];
}

void AdjMatrix::Show(){
if((int)a[0][0] == 0)
cerr<<"Error!矩阵不存在!\n";
else{
for(int i = 1;i <= a[0][0];i++){
for(int j = 1;j <= a[0][0];j++){
if(a[i][j] == INT_MAX)
cout<<setw(5)<<setprecision(7)<<"∞"<<'\t';
else
cout<<setw(5)<<setprecision(7)<<a[i][j]<<'\t';
}
cout<<endl;
}
}
}

void AdjMatrix::ShortestPath_Floyed(){
int Dim = (int)a[0][0],pre;
AdjMatrix A,Path;
this->Trs(Path);
Path.Trs(A);//取A=*(this)
for(int i = 1;i <= Dim;i++){
for(int j = 1;j <= Dim;j++)
Path.a[i][j] = -1;
}
for(int k = 1;k <= Dim;k++){
for(int i1 = 1;i1 <= Dim;i1++)
for(int j1 = 1;j1 <= Dim;j1++)
if(A.a[i1][j1] > A.a[i1][k]+A.a[k][j1]){
A.a[i1][j1] = A.a[i1][k]+A.a[k][j1];
Path.a[i1][j1] = k;
}
}
cerr<<"↘Floyed算法求解如下:\n";
for(int i2 = 1;i2 <=Dim;i2++){//输出最短路径
for(int j2 = 1;j2 <=Dim;j2++)
if(i2 != j2){
cout<<" "<<i2<<"->"<<j2<<": ";
if(A.a[i2][j2] == INT_MAX){
if(i2 != j2)
cout<<"不存在路径!\n";
}
else{
cout<<"路径长度："<<setw(3)<<A.a[i2][j2]<<" ";
cout<<"路径："<<i2<<"->";
pre = (int)Path.a[i2][j2];
while(pre != -1){
cout<<pre<<"->";
pre = (int)Path.a[pre][j2];
}
cout<<j2<<endl;
}
}
}
}

void AdjMatrix::ShortestPath_Dijkstra(int v){
int Dim = (int)a[0][0];
AdjMatrix A,temp;
this->Trs(temp);
temp.Trs(A);//取A=*(this)
int *s, *path,u,pre;
s = new int[Dim+1],path = new int[Dim+1];
s[0]=0,path[0]=0;
double *dist,mindis;
dist = new double[Dim+1];
dist[0] = 0.0;
for(int k = 1;k <= Dim;k++){
dist[k] = A.a[v][k];//距离初始化
s[k] = 0;//s[]置空
if(A.a[v][k] < INT_MAX)//路径初始化
path[k] = v;
else
path[k] = -1;
}
s[v] = 1,path[v] = 0;//源点编号v放入s中
for(int i = 1;i <= Dim;i++){//循环直到所有顶点的最短路径都求出
mindis = INT_MAX;
u = -1;
for(int j = 1;j <= Dim;j++){//选取不在s中且具有最小距离的顶点u
if(s[j] == 0 && dist[j] < mindis){
u = j;
mindis = dist[j];
}
}
if(u != -1){
s[u] = 1;
for(int r = 1;r <= Dim;r++)
if(s[r] == 0)
if(A.a[u][r] < INT_MAX && dist[u]+A.a[u][r] < dist[r]){
dist[r] = dist[u]+A.a[u][r];
path[r] = u;
}
}
}
cout<<"↘Dijkstra算法求解如下：\n";
Stack<int> st;
for(int i1 = 1;i1 <= Dim;i1++){//输出最短路径的长度，路径逆序输出
if(i1 != v){
cout<<" "<<v<<"->"<<i1<<": ";
if(s[i1] == 1){
cout<<"路径长度："<<setw(3)<<dist[i1]<<" ";
pre = i1;
cout<<"路径：";
while(pre != v){//一直回溯到初始顶点
st.Push(pre);
pre = path[pre];
}
st.Push(pre);
while(0 < st.GetTop() ){
cout<<st.Pop()<<"->";
}
cout<<st.Pop()<<endl;
}
else
cout<<"不存在路径!\n";
}
}
}

// LinkGraph.h: interface for the LinkGraph class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_LINKGRAPH_H__711D918A_0412_49B6_A496_B78EAAB3C611__INCLUDED_)
#define AFX_LINKGRAPH_H__711D918A_0412_49B6_A496_B78EAAB3C611__INCLUDED_

#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include "Stack.h"

#define INT_MAX 0x7FFFFFFF

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

struct EdgeNode{ //每一个顶点建立的单链表中结点的类型
int index; //邻接点序号
double value; //边的权值
EdgeNode *next;//下一条边的顶点
EdgeNode(EdgeNode *ne = NULL):next(ne){}//可选择参数的默认构造函数
};
struct VertexNode{ //单链表中头结点类型
char name[32]; //结点信息
int indegree; //入度计数域
EdgeNode *link;//指向第一条边结点
VertexNode(EdgeNode *li = NULL):link(li){}//可选择参数的默认构造函数
};

class LinkGraph{//图的邻接表类
private:
int num;//实际顶点数
VertexNode *adjlist;//单链表头结点数组
public:
LinkGraph(char **names = NULL,double **matrix = NULL,int n = 0){
num = n;
if(names){
EdgeNode *p1,*p2;
int *temp;
temp = new int[num];
for(int k = 0;k < num;k++)
temp[k] = 0;
adjlist = new VertexNode[num];
for(int i = 0;i < num;i++){
strcpy(adjlist[i].name,*(names+i));
for(int j = 0;j < num;j++){
if(matrix[j][i] != 0)
temp[i]++;
if(matrix[i][j] != 0){
adjlist[i].indegree++;
p1 = new EdgeNode;
p1->index = j;
p1->value = matrix[i][j];
if(!adjlist[i].link){
adjlist[i].link = p1;
p2 = p1;
}
else{
p2->next = p1;
p2 = p1;
}
}
}
adjlist[i].indegree = temp[i];
}
}
else
adjlist = NULL;
}
virtual ~LinkGraph();
void Show();
void TopologicalSort();
};

#endif // !defined(AFX_LINKGRAPH_H__711D918A_0412_49B6_A496_B78EAAB3C611__INCLUDED_)
// LinkGraph.cpp: implementation of the LinkGraph class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "LinkGraph.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

LinkGraph::~LinkGraph(){
EdgeNode *p1,*p2;
if(adjlist){
for(int i = 0;i < num;i++){
p1 = adjlist[i].link;
while(p1){
p2 = p1->next;
delete p1;
p1 = p2;
}
}
}
delete []adjlist;
}

void LinkGraph::Show(){
EdgeNode *temp;
if(adjlist){
for(int i = 0;i < num;i++){
if(adjlist[i].link)
cout<<" "<<adjlist[i].name<<":: ";
else
cout<<" "<<adjlist[i].name<<" ";
temp = adjlist[i].link;
while(temp){
cout<<adjlist[temp->index].name<<" ";
temp = temp->next;
}
cout<<endl;
}
}
}

void LinkGraph::TopologicalSort(){
Stack<int> st;
EdgeNode *temp;
int j,k,tag = 0;
for(int i = 0;i < num;i++){
if(adjlist[i].indegree == 0)
st.Push(i);
}
cout<<"↘拓扑排序算法求解如下：\n";
while(!st.IsEmpty()){
j = st.Pop();

if(tag%6 == 0)
cout<<"\n ";
tag ++;
if(tag != num)
cout<<adjlist[j].name<<" -> ";
else
cout<<adjlist[j].name<<endl;
temp = adjlist[j].link;
while(temp){
k = temp->index;
adjlist[k].indegree --;
temp = temp->next;
if(adjlist[k].indegree == 0)
st.Push(k);
}
}
if(num == tag)
cout<<"\n 拓扑排序成功!\n";
else
cout<<"\n 失败,有向图中存在环!\n";
}
// Exercise_4.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include "AdjMatrix.h"
#include "LinkGraph.h"

#define MAXSIZE1 6
#define MAXSIZE2 11

void DisplayMenu();

int main(int argc, char* argv[]){
DisplayMenu();
double a[MAXSIZE1][MAXSIZE1] = { 0, 50, 10,INT_MAX,INT_MAX,INT_MAX,
INT_MAX, 0, 15, 50, 10,INT_MAX,
20, 70, 0, 15,INT_MAX,INT_MAX,
INT_MAX, 20,INT_MAX, 0, 35,INT_MAX,
INT_MAX,INT_MAX,INT_MAX, 30, 0,INT_MAX,
INT_MAX,INT_MAX,INT_MAX, 3,INT_MAX, 0};
char str[MAXSIZE2][32] = {"程序设计","数值分析","普通物理","高等数学","数据结构",
"人工智能","编译原理","操作系统","计算机原理","线性代数","离散数学"};
double b[MAXSIZE2][MAXSIZE2] = {0,1,0,0,1,0,1,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,0,0,
0,1,1,0,0,0,0,0,0,1,0,
0,0,0,0,0,1,1,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0};
double **matrix1;
Make2DArray(matrix1,MAXSIZE1,MAXSIZE1);
for(int i1 = 0;i1 < MAXSIZE1;i1++){
for(int j1 = 0;j1 < MAXSIZE1;j1++)
matrix1[i1][j1] = a[i1][j1];
}
AdjMatrix A(matrix1,MAXSIZE1);
cout<<"↘邻接矩阵：\n";
A.Show();
cout<<"*******************************************************************************\n";
A.ShortestPath_Floyed();
cout<<endl;
A.ShortestPath_Dijkstra(2);

char **names;
Make2DArray(names,MAXSIZE2,12);
for(int s = 0;s < MAXSIZE2;s++){
strcpy(*(names+s),*(str+s));
}
double **matrix2;
Make2DArray(matrix2,MAXSIZE2,MAXSIZE2);
for(int i2 = 0;i2 < MAXSIZE2;i2++){
for(int j2 = 0;j2 < MAXSIZE2;j2++)
matrix2[i2][j2] = b[i2][j2];
}
LinkGraph Graph(names,matrix2,MAXSIZE2);
cout<<"*******************************************************************************\n";
cout<<"↘邻接表：\n";
Graph.Show();
cout<<endl;
Graph.TopologicalSort();
return 0;
}

void DisplayMenu(){
char *menu[]={
" ☆☆ 图 ☆☆ ",
" 1. Floyed算法 2. Dijkstra算法 3. 拓扑排序算法 ",
NULL
};
for(int i=0;menu[i];i++)
cout<<menu[i]<<'\n';
}

Answer 2

这是典型的最小生成树
#include<iostream>
using namespace std;
const int N1=27;
const int N2=76;
int fa[N1];
struct MST{
int x,y,cost;
}tree[N2];
int find(int i)
{
if(fa[i]==-1)return i;
else return fa[i]=find(fa[i]);
}
int jiao(const void *a,const void *b)
{
if((*(MST *)a).cost>(*(MST *)b).cost)return 1;
else return -1;
}
int yun(int i,int x)
{
int h,j,k,z1,z2,s,y;
memset(fa,-1,sizeof(fa));
qsort(tree,i,sizeof(MST),jiao);
for(h=0,s=0,j=0;j<x-1;h++){
z1=find(tree[h].x);
z2=find(tree[h].y);
if(z1!=z2){
cout<<tree[h].x<<' ';
cout<<tree[h].y<<endl;
s+=tree[h].cost;
fa[z1]=z2;
j++;
}
}
cout<<s<<endl;
return 0;
}
int init(void)
{
int i,j,k,x,y,n1,n2,n3;
char c1,c2;
i=0;
for(k=1;k<x;k++){
cin>>c1>>y;
n1=c1-'A'+1;
for(j=1;j<=y;j++){
cin>>c2>>n3;
n2=c2-'A'+1;
tree[i].x=n1;
tree[i].y=n2;
tree[i].cost=n3;
i++;
}
}
yun(i,x);
return 0;
}
int main(void)
{
freopen("zx.in","r",stdin);
freopen("zx.out","w",stdout);
init();
return 0;
}
输入
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
输出最小生成树的组成边的两端节点，及最小生成树的权值和
2 9
2 3
1 2
3 4
7 8
8 9
5 7
5 6
216
给点分吧

Answer 3

动态规划算法