구현 - 다익스트라 dijkstra, 플로이드 floyd

main.cpp

#include "WGraphDijkstra.h"
#include "WGraphFloyd.h"
int main()
{
 
    WGraphDijkstra g;
    g.load(ifstream("grap.txt"));
 
    g.display();
    cout << endl;
 
    g.dijkstra_path(0);
 
 
    WGraphFloyd f;
    f.load(ifstream("grap.txt"));
 
    f.display();
    cout << endl;
 
    f.floyd_path();
    f.printResult();
}

코드 출처 : c++로 쉽게 풀어쓴 알고리즘

#pragma once
#include "WGraph.h"
 
class WGraphFloyd : public WGraph
{
    int dist[MAX_VTXS][MAX_VTXS];
public:
 
    void floyd_path()
    {
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j)
                dist[i][j] = getEdge(i, j);
 
        for (int k = 0; k < size; ++k)
        {
            for (int i = 0; i < size; ++i)
                for (int j = 0; j < size; ++j)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        }
    }
    void printResult()
    {
        for (int i = 0; i < size; ++i)
        {
            for (int j = 0; j < size; ++j)
                cout << setw(4) << dist[i][j];
            cout << endl;
        }
        cout << endl;
    }
};

#pragma once
#include "WGraph.h"
 
class WGraphDijkstra : public WGraph
{
    int dist[MAX_VTXS];
    bool found[MAX_VTXS];
public:
    int nearest_vtx_idx()
    {
        int min = INF;
        int minIndex = -1;
        for (int i = 0; i < size; ++i)
        {
            if (dist[i] < min && !found[i])
            {
                min = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
    void print_distances()
    {
        for (int i = 0; i < size; ++i)
        {
            cout << dist[i] << " ";
        }
        cout << endl;
    }
 
    void dijkstra_path(int start)
    {
        for (int i = 0; i < size; ++i)
        {
            dist[i] = getEdge(start, i);
            found[i] = false;
        }
        found[start] = true;
        dist[start] = 0;
        for (int i = 0; i < size; ++i)
        {
            cout << "Step : " << i + 1 << endl;
            print_distances();
            int u = nearest_vtx_idx();
            found[u] = true;
            for (int w = 0; w < size; ++w)
            {
                if (found[w] == false)
                {
                    if (dist[u] + getEdge(u, w) < dist[w])
                        dist[w] = dist[u] + getEdge(u, w);
                }
            }
        }
    }
};