Dijkstra最小路径
第一次发帖..不知道这个对大家有没有用...PS:程序是在数学建模时写的...自己比较懒,所以改了别了的主要部分..输入主要是按建模时的要求..
/*
输入要求:第一个数为顶点总数,第二个为边的总数.
以下分别是一行三个数的"顶点,顶点,权值"
所有边的下一行为要求顶点到顶点最小路径的总数.
再以下几行,就为要求的顶点.
例:
4 4
1 2 2
1 4 4
2 3 4
3 4 2
2
1 3
2 4
*/
#include <iomanip>
#include <iostream>
#include <cstdlib>
#include<fstream>
using namespace std;
struct Node
{
int fr;
int to;
double weight;
struct Node *next;
};//邻接表的简单结构体.
void Dijkstra(int n,int v,double dist[],double prev[],double **c)
{
double maxint = 65535.0;
int i,j;
bool *s = new bool[n];
for ( i = 1; i <= n; i++)
{
dist[i] = c[v][i];
s[i] = false;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = true;
for ( i = 1; i < n; i++)
{
double temp = maxint;
int u = v;
for ( j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = true;
for ( j = 1; j <= n; j++)
{
if ((!s[j]) && (c[u][j] < maxint))
{
double newdist = dist[u] + c[u][j];
if (newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
int main()
{
int n,v,u,sum;
int q = 0;
int i,j,t;
int m;//n为顶点数,m为边数
ifstream fin("input.txt",ios::in);
if(!fin)
cout<<"can't open input.txt";
fin>>n>>m;
Node *root=new Node;
Node *p;
fin>>root->fr;
fin>>root->to;
fin>>root->weight;
root->next=NULL;
p=root;
while(m!=1)
{
Node *pp = new Node;
pp->next=NULL;
fin>>pp->fr;
fin>>pp->to;
fin>>pp->weight;
p->next=pp;
p=pp;
m--;
}//生成邻接表
int *way = new int[n + 1];
double **c = new double *[n + 1];
for ( i = 1; i <= n; i++)
{
c[i] = new double[n + 1];
}//生成二维动态数组
for ( j = 1; j <= n; j++)
{
for ( t = 1; t <= n; t++)
{
c[j][t]=65535.0;
if(j==t)
c[j][t]=0;
}
}//初始化二维数组
Node *pt=root;
while(pt)
{ c[pt->fr][pt->to]=pt->weight;
c[pt->to][pt->fr]=pt->weight;
pt=pt->next;
}//邻接表到邻接矩阵的转换
ofstream fout("output.txt",ios::out);
double *dist = new double [n+1];
double *prev = new double [n+1]; //申请空间不足时可以通过DEBUG,但会崩溃 .所以为[n+1]
fin>>sum;
while(sum)
{
fin>>v>>u;
Dijkstra(n, v, dist, prev, c);
int w = u;
q=0;
while (w != v)
{
q++;
way[q] = prev[w];
w = prev[w];
}
fout <<"最短路径从" <<v <<" -> " <<u ;
fout <<"路径为：";
for ( j = q; j >= 1; j--)
{
fout <<way[j] <<" ->";
}
fout <<u <<endl;
fout<<" 费用:" <<showpoint<<dist[u] <<endl;
--sum;
} //end while
delete []way;
for ( i = 1; i <= n; i++)
delete []c[i];
delete []c;
delete []dist;
delete []prev;
return 0;
} //申请空间不足时可以通过DEBUG,但会崩溃..原因是申请空间太少了.所以
