Տրված է չուղղորդված և կշռված գրաֆ, որի բոլոր գագաթների/կողերի կշիռները դրական թվեր են։ Տրված է նաև s բնական թիվը, որը համապատասխանում է գրաֆի մի ինչ-որ գագաթի։ Գտել s գագաթից դեպի մյուս գագաթները ընկած կարճագույն ճանապարհները։

main.cpp

#include <iostream>
#include <limits.h>
#include <stdlib.h>
#include <queue>

struct node
{
	int d;
	int w;
	node* next;
};

struct adj_list
{
	node* h;
};

struct graph
{
	int v;
	adj_list* a;
};

struct node* add_new_node(int data, int weigth)
{
	struct node* n = (struct node*)malloc(sizeof(struct node));
	n->d = data;
	n->w = weigth;
	n->next = 0;
}

graph* create_graph(int vv)
{
	graph* g = (struct graph*)malloc(sizeof(struct graph));
	g->v = vv;
	g->a = (struct adj_list*)malloc(vv * sizeof(struct adj_list));
	for(int i = 0; i < vv; ++i)
	{
		g->a[i].h = 0;
	}
	return g;
}

void add_edge(graph* g, int src, int dst, int weigth)
{
	struct node* n = add_new_node(dst, weigth);
	n->next = g->a[src].h;
	g->a[src].h = n;
	struct node* nn = add_new_node(src, weigth);
	nn->next = g->a[dst].h;
	g->a[dst].h = nn;
}

int dijkstra(struct graph* g, int s)
{
	std::priority_queue<std::pair<int, int> > q;
	int ss = g->v;
	int d[ss];
	int p[ss];
	for(int i = 0; i < ss; ++i)
	{
		d[i] = INT_MAX;
	}
	q.push (std::make_pair (0, s));
	d[s] = 0;
	while(!q.empty())
	{
		int w = q.top().first;
		int n = q.top().second;
		q.pop();
		struct node* c = g->a[n].h;
		while(c != 0)
		{
			if(d[c->d] > d[n] + c->w)
			{
			    d[c->d] = d[n] + c->w;
				p[c->d] = n;
			    q.push(std::make_pair(d[c->d], c->d));	
			}
			c = c->next;
		}
	}
	for(int i = 0; i < ss; ++i)
	{
		std::cout << d[i] << " ";
	}
	std::cout << std::endl;
}

int main()
{
	struct graph* g = create_graph(5);
 	add_edge(g, 0, 1, 5);
	add_edge(g, 0, 4, 10);
	add_edge(g, 1, 4, 2);
	add_edge(g, 1, 2, 2);
	add_edge(g, 1, 3, 7);
	add_edge(g, 2, 3, 6);
	add_edge(g, 3, 4, 1);
	dijkstra(g, 0);
	return 0;
}