大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > Dijkstra最小路径

Dijkstra最小路径

关键词:Dijkstra最小路径  阅读(874) 赞(39)

[摘要]本文是对Dijkstra最小路径算法的实现代码,与大家分享。
/*
输入要求:第一个数为顶点总数,第二个为边的总数.
以下分别是一行三个数的"顶点,顶点,权值"
所有边的下一行为要求顶点到顶点最小路径的总数.
再以下几行,就为要求的顶点.
例: 
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,但会崩溃..原因是申请空间太少了.所以


相关评论