Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 14.12.2018, 12:54   #1
azunight
 
Регистрация: 02.10.2018
Сообщений: 6
По умолчанию Алгоритм дейкстры

Здраствуйте, у меня есть код, реализующий алгоритм дейкстры. Как мне сделать так, чтобы я мог выводить в программе, какие пути есть и какие затраты требуются на каждый из них?
Вот код
Код:

#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#include <iostream>
#define INFINITY 9999
#define MAX 10
 
void dijkstra(int G[MAX][MAX], int n, int startnode);
 
int main()
{
    int G[MAX][MAX], i, j, n, u;
    printf("Enter no. of vertices:");
    scanf_s("%d", &n);
    printf("\nEnter the adjacency matrix:\n");
    
 
    for (i = 0; i<n; i++)
        for (j = 0; j<n; j++)
            scanf_s("%d", &G[i][j]);
    
 
    printf("\nEnter the starting node:");
    scanf_s("%d", &u);
    dijkstra(G, n, u);
 
    return 0;
}
 
void dijkstra(int G[MAX][MAX], int n, int startnode)
{
 
    int cost[MAX][MAX], distance[MAX], pred[MAX];
    int visited[MAX], count, mindistance, nextnode, i, j;
 
    
    for (i = 0; i<n; i++)
        for (j = 0; j<n; j++)
            if (G[i][j] == 0)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = G[i][j];
 
    
    for (i = 0; i<n; i++)
    {
        distance[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }
 
 
    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;
 
    while (count<n - 1)
    {
        mindistance = INFINITY;
 
        
        for (i = 0; i<n; i++)
            if (distance[i]<mindistance && !visited[i])
            {
                mindistance = distance[i];
                nextnode = i;
            }
 
               
        visited[nextnode] = 1;
        for (i = 0; i<n; i++)
            if (!visited[i])
                if (mindistance + cost[nextnode][i]<distance[i])
                {
                    distance[i] = mindistance + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        count++;
    }
 
    
    for (i = 0; i<n; i++)
        if (i != startnode)
        {
            printf("\nDistance of node%d=%d", i, distance[i]);
            printf("\nPath=%d", i);
 
            j = i;
            do
            {
                j = pred[j];
                printf("<-%d", j);
            } while (j != startnode);
        }
 
    
    system("pause");    
}
azunight вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм Дейкстры Малайка Общие вопросы Delphi 3 13.02.2016 20:18
С. Алгоритм Дейкстры XeniaZharinova Помощь студентам 0 26.12.2013 12:36
Алгоритм Дейкстры Kharass Помощь студентам 3 03.03.2013 16:38
Алгоритм Дейкстры tarnis Общие вопросы Delphi 4 11.05.2010 14:00
Алгоритм Дейкстры Dimon88 Помощь студентам 2 03.11.2007 17:13