哈夫曼编码

[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;
}