dijkstra

dijkstra.cpp

#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;

#define INF 1e9

class Graph{
	struct edge_t{
		edge_t(int v_, int dist_):v(v_), dist(dist_){;};
		int v;
		int dist;
	};
	struct vertex_t{
		int dist;
		int prev;
		vector<edge_t> edges;
	};
	vector<vertex_t> g;
public:
	Graph(int N): g(N){
		for(int i=0;i<g.size();i++){
			g[i].dist = INF;
			g[i].prev = -1;
		}
	};
	void add_edge(int from, int to, int dist)
	{
		g[from].edges.push_back(edge_t(to,dist));
		g[to].edges.push_back(edge_t(from, dist));
	};
	int dijkstra(int s /*source*/, int t/*sink*/, vector<int> &route)
	{
		priority_queue< pair<int,int> , vector< pair<int,int> >, greater< pair<int,int> > > que;
		g[s].dist = 0;
		que.push(make_pair(g[s].dist, s));
		while(!que.empty()){
			pair<int, int> head = que.top();
			que.pop();
			int dist = head.first;
			int v = head.second;
			if(dist != g[v].dist){
				continue;
			}
			printf("v=%d, dist=%d\n", v, dist);
			for(int i=0;i<g[v].edges.size();i++){
				edge_t edge = g[v].edges[i];
				// printf("i=%d, edge.v=%d, edge.dist=%d\n", i, edge.v, edge.dist);
				if(dist + edge.dist < g[edge.v].dist){
					g[edge.v].prev = v;
					g[edge.v].dist = dist + edge.dist;
					que.push(make_pair(g[edge.v].dist, edge.v));
					// printf("pushing dist:%d, v:%d\n", g[edge.v].dist, edge.v);
				}
			}
		}
		for(int v=t;v!=-1;v=g[v].prev){
			route.push_back(v);
		}
		return g[t].dist;
	};
};

int main(void)
{
	Graph g(6);
	g.add_edge(0, 1, 1);
	g.add_edge(1, 2, 1);
	g.add_edge(2, 3, 1);
	g.add_edge(2, 4, 10);
	g.add_edge(3, 4, 1);
	g.add_edge(4, 5, 1);
	vector<int> route;
	int ret = g.dijkstra(0, 5, route);
	for(int i=0;i<route.size();i++){
		printf("route[%d]=%d\n", i, route[i]);
	}
	printf("ret=%d\n", ret);

	{
		Graph g(7);
		int e[][3] = {{0,1,2}, {0,2,5}, {1,2,4}, {1,3,6}, {2,3,2}, {1,4,10}, {4,5,3}, {3,5,1}, {4,6,5}, {5,6,9}};
		for(int i=0;i<sizeof(e)/sizeof(e[0]);i++){
			g.add_edge(e[i][0], e[i][1], e[i][2]);
		}
		vector<int> route;
		int ret = g.dijkstra(0,6,route);
		for(int i=0;i<route.size();i++){
			printf("route[%d]=%d\n", i, route[i]);
		}
		printf("ret=%d\n", ret);
	}
	
		
	return 0;
}