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);
}