無権最短力アドレス:http://blog.csdn.net/midgard/article/details/4152336

                 ：Dijkstra  ，               。

  ：              。

     ，Dijkstra        v，    unknown        distance，       s v        known。
              ，          （known  ），        ，               。          。            。
           ，        ，              。
  
  
      s v1。
 ，         v1，    0，      known，
            
    1： known(v1)    unknown(v2,v3,v4,v5,v6,v7);       known    ，v4           ，    1，  v4 known
            
            
    2： known(v1,v4) unknown(v2,v3,v5,v6,v7);          known    ，v2           ，    2，  v2 known
            
    3： known(v1,v4,v2) unknown(v3,v5,v6,v7);          known    ，v3，v5           ，    3,   v3，v5 known
              
    4:  known(v1,v4,v2,v3,v5) unknown(v6,v7);          known    ，v7           ，    5,   v7 known
            
    5:  known(v1,v4,v2,v3,v5,v7) unknown(v6);          known    ，v6           ，    6,   v6 known
            // Map.cpp :              。

//

#include "stdafx.h"

#include 
using namespace std;

#define MAX_VERTEX_NUM    20
#define INFINITY    2147483647 
struct adjVertexNode 
{
	int adjVertexPosition;
	int weight;
	adjVertexNode* next; 
};
struct VertexNode
{
	char data[2];
	int distance;
	bool known;
	VertexNode* path;
	adjVertexNode* list;
}; 
struct Graph
{
	VertexNode VertexNode[MAX_VERTEX_NUM];
	int vertexNum;
	int edgeNum;
};

void CreateGraph (Graph& g)
{
	int i, j, edgeStart, edgeEnd, edgeWeight;
	adjVertexNode* adjNode;
	cout << "Please input vertex and edge num (vnum enum):" <> g.vertexNum >> g.edgeNum;
	cout << "Please input vertex information (v1)/n note: every vertex info end with Enter" <> g.VertexNode[i].data; // vertex data info.
		g.VertexNode[i].list=NULL; 
	}
	cout << "input edge information(start end weight):" <>edgeStart >>edgeEnd >> edgeWeight; 
		adjNode = new adjVertexNode; 
		adjNode->weight = edgeWeight;
		adjNode->adjVertexPosition = edgeEnd-1; // because array begin from 0, so it is j-1
		//            Vi     ,     ！！！    。
		adjNode->next=g.VertexNode[edgeStart-1].list; 
		g.VertexNode[edgeStart-1].list=adjNode; 
	}
}

void PrintAdjList(const Graph& g)
{
	for (int i=0; i < g.vertexNum; i++)
	{
		cout<< g.VertexNode[i].data << "->";
		adjVertexNode* head = g.VertexNode[i].list;
		if (head == NULL)
			cout << "NULL";
		while (head != NULL)
		{
			cout << head->adjVertexPosition + 1 <next;
		}
		cout << endl;
	}
}
void DeleteGraph(Graph &g)
{
	for (int i=0; inext;
			delete tmp;
			tmp = NULL;
		}
	}
}
VertexNode* FindSmallestVertex(Graph& g)
{
	int smallest = INFINITY;
	VertexNode* sp = NULL;


	for (int i=0; iknown = true;
		adjVertexNode* head = v->list;
		while (head != NULL)
		{
			VertexNode* w = &g.VertexNode[head->adjVertexPosition];
			if( !(w->known) )
			{
				if(v->distance + head->weight < w->distance)
				{
					w->distance = v->distance + head->weight;
					w->path = v;
				}
			}
			head = head->next;
		}
	}
}
	void PrintPath(Graph& g, VertexNode* source, VertexNode* target)
	{
		if (source!=target && target->path==NULL)
		{
			cout << "There is no shortest path from " << source->data <data <path!=NULL)
			{
				PrintPath(g, source, target->path);
				cout << " ";
			}
			cout << target->data ;
		}
	}

	int main(int argc, const char ** argv)
	{
		Graph g;
		CreateGraph(g);
		PrintAdjList(g);
		VertexNode& start = g.VertexNode[0];
		VertexNode& end = g.VertexNode[6];
		Dijkstra(g, start);
		cout << "print the shortest path from v1 to v7" << endl;
		PrintPath(g, &start, &end);
		cout << endl;
		DeleteGraph(g);
		return 0;
	}