weightedgraph.h

data+structures+using+c的源码

#ifndef H_weightedGraph
#define H_weightedGraph

#include <iostream>
#include <fstream>
#include <iomanip>
#include "graphType.h"

using namespace std;

template<class vType, int size>
class weightedGraphType: public graphType<vType, size>
{ 
public:     
	void createWeightedGraph();
      //Function to create the graph and the weight matrix.
    void shortestPath(vType vertex);
      //Function to determine the smallest weight from the 
      //vertex, that is, the source to every other vertex 
       //in the graph.     
	void printShortestDistance(vType vertex);
      //Function to print the smallest weight from the 
      //source to all the other vertices in the graph.

 protected:     
	double weights[size][size];  //weight matrix     
	double smallestWeight[size]; //smallest weight from the
                                 //source to the other 
                                 //vertices
}; 


template <class vType, int size>
void weightedGraphType<vType, size>::createWeightedGraph()
{
	cout<<"Write the definition of the "
		<<"function createWeightedGraph"<<endl;
} //createWeightedGraph

template<class vType, int size>
void weightedGraphType<vType, size>::shortestPath(vType vertex)
{
    int i,j;
    int v;
    double minWeight;

    for(j = 0; j < gSize; j++)
        smallestWeight[j] = weights[vertex][j];

    bool weightFound[size];
    for(j = 0; j < gSize; j++)
        weightFound[j] = false;

    weightFound[vertex] = true;
    smallestWeight[vertex] = 0;

    for(i = 0; i < gSize - 1; i++)
    {
        minWeight = infinity;

        for(j = 0; j < gSize; j++)
            if(!weightFound[j])
               if(smallestWeight[j] < minWeight)
               {
                  v = j;
                  minWeight = smallestWeight[v];
               }

        weightFound[v] = true;

        for(j = 0; j < gSize; j++)
            if(!weightFound[j])
               if(minWeight + weights[v][j] < smallestWeight[j])
                  smallestWeight[j] = minWeight + weights[v][j];
    } //end for
} //end shortestPath

template<class vType, int size>
void weightedGraphType<vType, size>::printShortestDistance
                                    (vType vertex)
{
    cout<<fixed<<showpoint<<setprecision(2);

	cout<<"Source vertex: "<<vertex<<endl;
    cout<<"Shortest distance from the source to each vertex."
        <<endl;
    cout<<"Vertex Shortest_Distance"<<endl;

    for(int j = 0; j < gSize; j++)
        cout<<setw(4)<<j<<setw(12)<<smallestWeight[j]<<endl;
    cout<<endl;
}

#endif