用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

哈夫曼编码

2017-12-15 作者:柯侧耳倾听者举报

[c++]代码库

3 5 10
4 3 20
4 5 60
输出数据:
Adjacency Matrix:
  999999      10  999999      30     100
      10  999999      50  999999  999999
  999999      50  999999      20      10
      30  999999      20  999999      60
     100  999999      10      60  999999
The shortest distance from V1 to V5: 60
The shortest path from V1 to V5: 1 -> 4 -> 3 -> 5
*/
 
#include <iostream>
using namespace std;
 
const int maxnum = 100;
const int maxint = 999999;
 
 
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
    bool s[maxnum];    //signal of vertex put into S
    for(int i=1; i<=n; ++i)  //initialize
    {
        dist[i] = c[v][i];
        s[i] = 0;     //all vertices not used
        if(dist[i] == maxint)
            prev[i] = 0;
        else
            prev[i] = v;
    }
    dist[v] = 0;
    s[v] = 1;
 
    
    for(i=2; i<=n; ++i) //put vertices into S until all vertices put
    {
        int tmp = maxint;
        int u = v;
        
        for(int j=1; j<=n; ++j) //find minimum of dist[j]
            if((!s[j]) && dist[j]<tmp)
            {
                u = j;      // vertex number        
                tmp = dist[j];
            }
        s[u] = 1;    //signal of vertex put into S
 
        
        for(j=1; j<=n; ++j)  //update distance
            if((!s[j]) && c[u][j]<maxint)
            {
                int newdist = dist[u] + c[u][j];
                if(newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
    }
}
 
void searchPath(int *prev,int v, int u)
{
    int que[maxnum]; //vertices queue
    int tot = 1;
    que[tot] = u;
    tot++;  //total vertices
    int tmp = prev[u];
    while(tmp != v) 
    {
        que[tot] = tmp; //put the vertex into the queue
        tot++;
        tmp = prev[tmp];
    }
    que[tot] = v;
    for(int i=tot; i>=1; --i)
        if(i != 1)
            cout << que[i] << " -> ";
        else
            cout << que[i] << endl;
}
 
int main()
{
    int dist[maxnum];     
    int prev[maxnum];     
    int c[maxnum][maxnum];   
    int n, line;             
 
    
	cout << "Vertices: >";
    cin >> n;
    
	cout << "Lines: >";
    cin >> line;
    int p, q, len;          
 
   
    for(int i=1; i<=n; ++i) // not input distances all largest
        for(int j=1; j<=n; ++j)
            c[i][j] = maxint;
 
    for(i=1; i<=line; ++i)  //input vertices distances
    {
        cin >> p >> q >> len;
        if(len < c[p][q])       
        {
            c[p][q] = len;      
            c[q][p] = len;      
        }
    }
 
    for(i=1; i<=n; ++i) // not input distances all largest
        dist[i] = maxint;
	cout << "Adjacency Matrix:" << endl;
    for(i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
            printf("%8d", c[i][j]);
        printf("\n");
    }
 
    Dijkstra(n, 1, dist, prev, c);
 
    
    cout << "The shortest distance from V1 to V" << n << ": " << dist[n] << endl;
 
    
    cout << "The shortest path from V1 to V" << n << ": ";
    searchPath(prev, 1, n);
	return 0;
}


分享到:
更多

网友评论    (发表评论)

共1 条评论 1/1页

发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。