Dijkstraアルゴリズム--単一ノードからすべてのノードまでの最短距離

2206 ワード

primとよく似ています
#include <stdio.h>
#include <iostream>
using namespace std;

#define MAXLEN 10
#define INFINITE 0xffff
int d[MAXLEN];
int visited[MAXLEN] = {0};

int m_min(int x, int y)
{
    return ((x > y)? y : x);
}

void outputArray(int a[], int n)
{
	for (int i = 0; i < n; i++)
		cout<<a[i]<<" ";
	cout<<"
"; } //find the shortest distance from start node to all other nodes void dijkstr(int graph[][MAXLEN], int n, int start) { int i, j, min; for (i = 0; i < MAXLEN; i++) { d[i] = INFINITE; } int pos = start; d[pos] = 0; visited[pos] = 1; for (i = 0; i < n-1; i++) { min = n; //min is the shortest distance index, it's initialized to pos for (j = 0; j < n; j++) { if (!visited[j]) { d[j] = m_min (d[j], d[pos] + graph[pos][j]); if (d[min] > d[j]) min = j; } } pos = min; visited[pos] = 1; cout<<"after update, the d[] is:
"; outputArray(d, n); cout<<"select node "<<pos<<" from it, the shortest distance is "<<d[pos]<<"

"; } cout<<"output the result from node "<<start<<" to other node shortest distance:
"; for (j = 0; j < n; j++) { cout<<"d["<<start<<"] to d["<<j<<"] is:"<<d[j]<<endl; } } void main (void) { int len = 5; int graph[][MAXLEN] = { {0, 10, 3, INFINITE, INFINITE}, {INFINITE, 0, 1, 2, INFINITE}, {INFINITE, 4, 0, 8, 2}, {INFINITE, INFINITE, INFINITE, 0, 7}, {INFINITE, INFINITE, INFINITE, 9, 0} }; dijkstr(graph, 5, 1); }